【今日算法】4月18日-缺失的第一个正数-问答-阿里云开发者社区-阿里云

开发者社区> 问答> 正文

【今日算法】4月18日-缺失的第一个正数

2020-04-20 07:10:32 1035 1

今天分享的题目来源于 LeetCode 第 41 号问题:缺失的第一个正数。

题目描述

给定一个未排序的整数数组,找出其中没有出现的最小的正整数。

示例 1:

输入: [1,2,0]输出: 3

示例 2:

输入: [3,4,-1,1]输出: 2

示例 3:

输入: [7,8,9,11,12]输出: 1

说明:你的算法的时间复杂度应为O(n),并且只能使用常数级别的空间。

题目解析

这道题使用桶排序的思路,即 “一个萝卜一个坑”,就可以解决。可以就使用题目中的例子,在纸上写写画画,就能得出思路,只不过在编码上需要注意一些细节。

1.png

我们可以把数组进行一次“排序”,“排序”的规则是:如果这个数字 i 落在“区间范围里”,i 就应该放在索引为 i – 1 的位置上,下面具体解释。

1、数字 i 落在“区间范围里”;

例如:[3, 4, -1, 1],一共 4 个数字,那么如果这个数组中出现 “1”、“2”、“3”、“4”,就是我们重点要关注的数字了;

又例如:[7, 8, 9, 11, 12] 一共 5 个数字,每一个都不是 “1”、“2”、“3”、“4”、“5” 中的一个,因此我们无须关注它们;

2、i 就应该放在索引为i - 1 的位置上;

这句话也可以这么说 “索引为 i 的位置上应该存放的数字是 i + 1”。

就看上面那张图,数字 1 应该放在索引为 0 的位置上,数字 3 应该放在索引为 2 的位置上,数字 4 应该放在索引为 3 的位置上。一个数字放在它应该放的位置上,我们就认为这个位置是“和谐”的,看起来“顺眼”的。

按照以上规则排好序以后,缺失的第 1 个正数一下子就看出来了,那么“最不和谐”的数字的索引 +1,就为所求。

那如果所有的数字都不“和谐”,数组的长度 +1 就为所求。

动画描述

2.gif

图片描述

以下是上面 gif 图的静态图。

3.jpg

4.jpg

5.jpg

6.jpg

7.jpg

8.jpg

9.jpg

10.jpg

代码实现

public class Solution {

    // 关键字:桶排序,什么数字就要放在对应的索引上,其它空着就空着
    // 最好的例子:[3,4,-1,1]
    // 整理好应该是这样:[1,-1,3,4],
    // 这里 1,3,4 都在正确的位置上,
    // -1 不在正确的位置上,索引是 1 ,所以返回 2
    // [4,3,2,1] 要变成 [1,2,3,4]
    // 这里负数和大于数组长度的数都是"捣乱项"。
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;

        for (int i = 0; i < len; i++) {
            // 前两个是在判断是否成为索引
            // 后一个是在判断,例如 3 在不在索引 2 上
            // 即 nums[i] ?= nums[nums[i]-1] 这里要特别小心
            while (nums[i] > 0 && nums[i] <= len && nums[nums[i] - 1] != nums[i]) {
                // 第 3 个条件不成立的索引的部分是 i 和 nums[i]-1
                swap(nums, nums[i] - 1, i);
            }
        }

        // 调试代码
        // System.out.println(Arrays.toString(nums));

        for (int i = 0; i < len; i++) {
            // [1,-2,3,4]
            // 除了 -2 其它都满足:i+1 = num[i]
            if (nums[i] - 1 != i) {
                return i + 1;
            }
        }

        return len + 1;
    }

    private void swap(int[] nums, int index1, int index2) {
        if (index1 == index2) {
            return;
        }
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        // int[] nums = {3, 4, -1, 5};
        int[] nums = {4, 3, 2, 1};
        int firstMissingPositive = solution.firstMissingPositive(nums);
        System.out.println(firstMissingPositive);
    }
}

复杂度分析

  • 时间复杂度:푂(푁) ,这里 푁 是数组的长度,其实只要看这个数组一遍,就可以知道每个数字应该放在哪个位置,所以时间复杂度是 푂(푁) 。
  • 空间复杂度:푂(1) ,桶排序在原地进行,没有使用额外的存储空间。

来源 | 五分钟学算法

作者 | P.yh

取消 提交回答
全部回答(1)
相关问答

54

回答

阿里云已停止对MySQL5.1的版本维护,快快快升级版本吧

rds-pd 2014-11-12 16:21:57 62186浏览量 回答数 54

38

回答

干货分享:DBA专家门诊一期:索引与sql优化问题汇总

xiaofanqie 2014-12-25 15:13:38 92097浏览量 回答数 38

37

回答

阿里官方Java代码规范标准《阿里巴巴Java开发手册》下载

管理贝贝 2017-02-10 15:14:36 77738浏览量 回答数 37

8

回答

OceanBase 使用动画(持续更新)

mq4096 2019-02-20 17:16:36 337038浏览量 回答数 8

27

回答

阿里云开源软件镜像站点上线啦!!

qilu 2014-01-06 18:14:06 96108浏览量 回答数 27

11

回答

【精品问答合集】MongoDB热门问答

李博 bluemind 2019-05-29 16:50:19 121345浏览量 回答数 11

31

回答

【入门教程系列】Linux系统建站完整教程(适用于新手初级站长)

wujian8150 2011-09-26 16:53:51 49098浏览量 回答数 31

11

回答

速戳 | 20位阿里出题专家-备战阿里必不可少的题目

Runt 2020-04-15 10:54:04 57626浏览量 回答数 11

19

回答

云数据库RDS MySQL版【问答合集】

我是管理员 2018-08-03 15:10:37 48176浏览量 回答数 19

1

回答

阿里云各种产品使用索引(更新2015.08.17)

梦丫头 2015-07-18 12:19:16 71674浏览量 回答数 1
0
文章
103
问答
问答排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载