41. First Missing Positive

Posted on | In | 浏览 次
Words count in article: 579 | Reading time ≈ 2

题目

  • Given an unsorted integer array, find the smallest missing positive integer.

  • Example:

    1
    2
    Input: [7,8,9,11,12]
    Output: 1
  • Note: Your algorithm should run in O(n) time and uses constant extra space.

解题思路

  • 本题的题意比较容易理解，即寻找一个无序的数组里面找到一个最小缺失的正整数
  • 第一想法是将无序数组进行排序，然后遍历一遍排好序的数组即可找出最小缺失的正整数，但是排序算法最优解的时间复杂度都为O(nlogn)，显然不能满足题目的时间复杂度要求
  • 其次的主要想法就是利用数组的下标，因为下标是从0开始的，不断累增的数列，并且除0外都是正整数
    • 遍历数组，将当前元素交换到其减一后作为下标的位置，即nums[i]与nums[nums[i] - 1]进行交换，即将1放到数组0号位，将2放到数组1号位，依此类推。这个步骤比较关键，其中小坑也比较多，有些是提交了才发现的
      • 交换条件的选择，可能被交换的元素必须要满足> 0&&< array.size&&nums[i] != nums[nums[i] - 1],其中最后一个条件是避免两个位置不断的执行交换，例如输入[1,1]的情况，造成死循环
      • 循环变量的控制，当需要交换的时候需要将循环变量-1，或者说不发生交换的时候，循环变量+1
    • 再次遍历数组，将第一个下标 与对应位置元素 - 1不等的下标返回，若都相等，则返回数组的size + 1

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int minPos = 1;
        int size = nums.size(); 

        // 将满足条件的的元素进行交换，将元素放到数组下标等于该元素的位置
        for(int i = 0; i < size; ) {
            if(nums[i] < size && nums[i] >= 1 && nums[i] != nums[nums[i] - 1]) {
                int tmp = nums[nums[i] - 1];
                nums[nums[i] - 1] = nums[i];
                nums[i] = tmp;
            }
            else {
                ++i;
            }

        }
		
        // 遍历数组，寻找下标与对应位置不等的下标，此下标即为最小整数，否则则为size+1
        for(int i = 0; i < size; ++i) 
            if(i != nums[i] - 1)
                return i + 1;

        return size + 1;
    }
};