0%

LeetCode No.41 缺失的第一个正数

LeetCode No.41 缺失的第一个正数

LeetCode No.41 缺失的第一个正数

题目详情

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

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/first-missing-positive
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题解

首先想到一个能偷鸡但是特别蠢的方法,我们创建一个字符串,不断的往字符串中添加nums数组中的内容,并且在每个数字的左右加上逗号。加完后,让res从1开始不断的往上增加,每次都用s.contains("," + res + ",")进行判断,判断res这个数字是否出现在nums中。因为要找未出现的最小正整数,如果res不在了就知道最终的解就是当前的res。

虽然这样题目可以做出来,但是时间空间上….一言难尽

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int firstMissingPositive(int[] nums) {
int res = 1;
String s = ",";
for (int num : nums) {
s = s + num + ",";
}
while (true) {
if (!s.contains("," + res + ",")) {
return res;
} else {
res++;
}
}
}

接下来是比较正经的想法。

首先我们创建一个nums长度的桶(数组),遍历nums中的每一个数值,如果说这个数值大于0且小于nums的长度,就可以将桶内对应位置的数值变为1,说明这个位置的数字出现过了。当把nums全部排完了,再去遍历这个桶。从头开始找,找到第一个数值为0的地方,返回位置坐标。如果没找到,解就是nums最大长度+1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static int firstMissingPositive(int[] nums) {
//创建桶
int []res = new int[nums.length];
for (int num : nums) {
//遍历更新桶的数据
if (num > 0 && num<=nums.length) {
res[num-1] = 1;
}
}
// 找到第一个数值为0的,返回即可
for (int i = 1; i <= nums.length; i++) {
if(res[i-1]==0){
return i;
}
}
//桶里都是1,那解就是最大长度+1.
return nums.length+1;
}

显然用桶来做的话,速度快,但是内存消耗就爆炸多了。




======================
全 文 结 束    感 谢 阅 读
======================