41. First Missing Positive
2017-03-23 本文已影响175人
codingXue
问题描述
Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
问题分析
这是一道hard题,自己没有思路TAT,在网上搜了解答
分析题意
- 要找的是第一个不存在的正数,那么对于长度为n的输入,非正数和大于n的数都是没有用的。
- 要求用常数空间解决,因此不能另开数组,而应该在原数组上进行操作,这时应留意到,数组的下标是0到n-1,与我们考虑的正数范围1到n是一一对应的。
- 我们利用下标作为标记,将数组中每个在1到n之间的元素item,放在nums[item-1]的位置,然后第二次遍历数组,找到第一个nums[i] != i+1的位置,则i+1就是我们要找的first missing postive integer。
做法
- 第一次遍历数组,若nums[i]的值在1,n之间且nums[nums[i]-1] != nums[i],则交换nums[nums[i]-1]和nums[i]。nums[nums[i]-1] != nums[i]包含两层含义,1)如果nums[i] != i+1,则nums[i]-1 != i,那么nums[i]需要被调换到它应该去的位置;如果nums[nums[i]-1] == nums[i]说明待交换的两个数字相等,则不需交换,否则会死循环。需要注意的是,如果被换到nums[i]位置的数字依然符合交换条件,那么需要继续进行交换,也就是说这里不是一个if判断,而是一个while循环。
- 第二次遍历数组,找到第一个nums[i] != i+1的位置,返回i+1。
复杂度分析
虽然这个思想还是蛮好理解,但是在一个for循环里又出现了一个while循环,它的复杂度能是O(n)吗?其实是酱紫,算法复杂度应该看的是基本操作的次数,在这个问题里,基本操作指的是交换操作,而每次交换操作,都至少有一个数字去了它应该去的地方,那么一个n长度的数组,最多只需要n次交换操作,所以它的复杂度是O(n)的~
AC代码
class Solution {
public:
int firstMissingPositive(vector<int>& nums) {
int n = nums.size();
int i;
for (i = 0; i < n; i++){
while(nums[i] > 0 && nums[i] < n && nums[nums[i]-1] != nums[i]){
int tmp = nums[nums[i]-1];
nums[nums[i]-1] = nums[i];
nums[i] = tmp;
}
}
for (i = 0; i < n; i++){
if (nums[i] != i+1)
break;
}
return i+1;
}
};
Runtime: 3 ms, which beats 70.66% of cpp submissions.