HelloKenLee

Leetcode 41. First Missing Positive 解题报告

Posted on By KenLee

题目信息

题目: 41. First Missing Positive
难度: Hard
正确率: 25%
问题描述:

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.

Subscribe to see which companies asked this question.

问题分析

  该问题的大意是给出一个数组,让你返回从小到大排序后的第一个缺失的正数。一开始没读懂题目,以为返回的是第一个缺失的数,后来才发现一定要返回正数,0也不算,因此还需要特殊处理。还有题目没有说清楚的就是数组允许有重复的数字,也就是说比如[1,1,3,3,5]这样的输入也是合法的。

解题思路

  最简单的思路当然是sort()一遍然后找第一个缺失的正数啦,不过题目明确要求要O(N)的时间复杂度,肯定不能排序。最直接的思路就是进行哈希了,不过有一个比较诡异的地方就是题目要求常数的额外空间。因此使用unordered_map基本上是没戏的。
  一个比较好的思路是我直接在原数组进行哈希,假设数组长度为N,数组的最小值为min,那么这个数组在[min, min+N]的这个区间内必定会有First Missing Number,只要筛选出第一个正数就是题目所求的结果。因此算法就是在原来的数组上建立[min,min+N]的一个表,其中第0位表示最小的数。
  但是通过进一步思考我们可以发现,在该问题中,负数都是没有意义的。换而言之,我们的First Missing Positive肯定会出现在区间[0,N]之中,其中N为数组长度。这样子看来,我们只需要建立[0,N]的哈希表即可。唯一要注意的就是对于负数和超过N的数这类不合法的数要进行特殊处理。   因此算法可以表示为:
  对于数组的每一个数,我们做以下处理:

  1. 如果该数正确(num[i]==i),或者该数不合法(num[i]<0 || num[i] > N),我们不做处理。
  2. 如果该数合法但是不正确(num[i]∈[0,N]num[i]!=i),则它放到正确的位置上(num[i]num[num[i]]),直到num[i]==i
      最后扫一遍找到第一个不正确或不合法数,返回其下标。
      值得一提的是,如果有重复的数,把多余的数当做不合法数据处理;另外先向数组中push一个0是为了避免数组为空的情况。

结果分析

  • 时间复杂度: 因为每一个数可以在O(1)的时间内被交换到正确的位置之后就不会发生改变,总共有N个数,复杂度为O(N)
  • 空间复杂度: O(1),没有用到额外空间。
  • 通过时间: 6 ms
  • 击败: 16.14%的提交

源代码

class Solution {
public:
    // 在数组内进行交换,把数组本身当作一个哈希表
    int firstMissingPositive(vector<int>& nums) {
        nums.push_back(0);
        int i = 0;
        while(i < nums.size()) {
            int rightPos = nums[i];
            if(nums[i] > 0 && rightPos != i && rightPos < nums.size() && nums[rightPos] != rightPos) {
                swap(nums[i], nums[rightPos]);
            } else {
                ++i;
            }
        }
        for( int i = 1; i < nums.size(); ++i) {
            if(nums[i] != i){
                return i;
            }
        }
        return nums.size();
    }
};