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

Example 1:

Input: [1,2,0]Output: 3

Example 2:

Input: [3,4,-1,1]Output: 2

Example 3:

Input: [7,8,9,11,12]Output: 1

Note:

Your algorithm should run in O(n) time and uses constant extra space.

 

 AC code:

class Solution {public:    int firstMissingPositive(vector
               
                & nums) {        int len = nums.size();        for (int i = 0; i < len; ++i) {            while (nums[i] > 0 && nums[i] <= len && nums[nums[i]-1] != nums[i]) {                int temp = nums[nums[i]-1];                nums[nums[i]-1] = nums[i];                nums[i]  = temp;            }        }        for (int i = 0; i < len; ++i) {            if (nums[i] != i + 1) {                return i+1;            }        }        return len+1;    }};
               

Runtime: 

0 ms, faster than 100.00% of C++ online submissions for First Missing Positive.

 

桶排序（Bucket sort）或所谓的箱排序，是一个，工作的原理是将分到有限数量的桶里。每个桶再个别排序（有可能再使用别的或是以递归方式继续使用桶排序进行排序）。桶排序是的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（{\displaystyle \Theta (n)}（））。但桶排序并不是，他不受到{\displaystyle O(n\log n)}下限的影响。

桶排序以下列程序进行：

1. 设置一个定量的数组当作空桶子。
2. 寻访序列，并且把项目一个一个放到对应的桶子去。
3. 对每个不是空的桶子进行排序。
4. 从不是空的桶子里把项目再放回原来的序列中。