本文共 804 字，大约阅读时间需要 2 分钟。

Given an unsorted integer array, find the smallest missing positive integer.Your algorithm should run in O(n) time and uses constant extra space.题意：求一个数组中最小的缺失正数。要求O(n)的时间复杂度和O(1)的空间复杂度。Example 1:Input: [1,2,0]Output: 3Example 2:Input: [3,4,-1,1]Output: 2Example 3:Input: [7,8,9,11,12]Output: 1Note:

思路：难点是O(n)的时间复杂度和O(1)的空间复杂度。因为是仅寻找第一个缺失的正数，所以若所有正数都在，则他们的值应该是1~nums.size()连续存在的。把每个值换到下标所在位置(使nums[i]==i+1)，第一个不在对应位置的正数即为缺失值。替换过程如下：

需要注意，若当前元素的值在范围(1~nums.size())之外，则不需要交换，肯定是无效值；此外若要交换的两个值相同，则也不能交换，一是没必要，因为该值已经在正确位置，二是不能换，因为会造成死循环。

int firstMissingPositive(vector
   
    & nums) {	int len = nums.size();	for (int i = 0; i
    
     = 1 && nums[i] <= nums.size() 			&& nums[i] != i + 1 && nums[i] != nums[nums[i] - 1])			swap(nums[i], nums[nums[i] - 1]);		else			i++;	}	//输出第一个不在位置上的正数	for (int i = 0; i
    
   

转载地址：http://mhwsi.baihongyu.com/