每日算法——leetcode系列

---

First Missing Positive

Difficulty: Hard

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.

class Solution {public:    int firstMissingPositive(vector
    
     & nums) {            }};
    

翻译

第一个缺失的正整数

难度系数：困难

给定一个无序数组，找出第一个缺失的正整数。

例如：给定[1,2,0] 返回 3,[3,4,-1,1] 返回 2。算法的时间复杂度为O(n), 空间复杂度为常数。

思路

此题一看想排序，如果有序后，找第一个缺失的正整数，那就从1开始查，如果数组中查到有1，那就查2，如此查到最后看待查的数就是要的结果，要查的数可以用索引来表示。

排序算法时间复杂度为O(n)的是桶排序，这里关键是要找到桶的个数，由于只查正整数，假定数组的长序为n，那n-1个桶放正整数就够了，遍历数组，小于1和大于n-1的数都不用管，这样就可以把数组中1到n-1的数剔出放在相应位置的桶中，再查缺失元素，但这种方案空间复杂度为O(n)，不为常数。下面分析排序：假定： 桶k装的数为m

• k == m 不变

• k != m 则数m应该装到第m个桶，则把桶m的数和桶k的数交换，直接交换过来的数为m就不用交换

  这里可能会给人感觉时间复杂度不为O(n)了，由于每一次交换后都会把一个数放到正确的桶上，所以平均下来最后还是O（n）

代码

class Solution {public:    int firstMissingPositive(vector
    
     & nums) {                // sort        int n = static_cast
     
      (nums.size());        int num;        for(int i = 0; i < n; ++i) {            num = nums[i];            while (num > 0 && num < n && nums[num-1] != num) {                swap(nums[i], nums[num-1]);                num = nums[i];            }        }                // find        int wantToFind = 1;        for (auto &item : nums){            if (item == wantToFind){                ++wantToFind;            }        }        return wantToFind;    }};
     
    

唠叨

教初中娃儿编程真是一个难事，能力不足，想要培养一个孩子的编程兴趣还完全做不到