leecode 解题总结：41. First Missing Positive

#include <iostream>#include <stdio.h>#include <vector>#include <set>using namespace std;/*问题: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.分析：寻找首次丢失的整数，但是给定的数组可能含有0和负数。题目只能用O(n)时间，不能排序。应该是扫描一遍数组就算出答案。可以将不断扫描的数进行异或处理：比如: 1^2=3      1^3^4=0001 ^ 0011 ^ 0100 = 0010^0100=0110=6	  和1^2^3^4=0110^0010=0100=4也就是说可以将数组中整数进行异或处理得到sum1，获取数组中最大整数n,对1到n也异或处理得到sum2，将sum1与sum2进行异或处理，得到的结果如果为0，那么丢失的数为n+1;否则，丢失的整数为sum1^sum2未能求解出输入:3(数组元素个数)1 2 0(数组所有元素)43 4 -1 121 121000 -121 2输出32213关键:1 解法：设定一种映射A[i] = i + 1,比如1对应A[0]。如果找到某个元素A[i]，就将它和A[ A[i] -1 ]交换。        找到i从0开始找到第一个A[i] != i + 1的元素即可	//交换，在数组长度允许的条件下，将位置不符合的元素进行交换	if(1 <= value && value <= size && value != nums.at(value - 1))	{		swap(nums.at(i) ,nums.at(value - 1) );		//每次交换后，当前位置不一定符合，所以i--,再重新计算一次		i--;	}2 		//如果是空数组，返回1，等于丢失第一个整数		if(nums.empty())		{			return 1;		}3 如果数组中出现重复元素需要规避4 并不一定是最大数之前的元素都会出现*/class Solution {public:    int firstMissingPositive(vector<int>& nums) {		//如果是空数组，返回1，等于丢失第一个整数		if(nums.empty())		{			return 1;		}		int size = nums.size();		//防止出现重复元素		int value;		for(int i = 0 ; i < size ; i++)		{			//元素i+1在下标为i的位置上，则跳过			if(nums.at(i) == i + 1)			{				continue;			}			value = nums.at(i);			//交换，在数组长度允许的条件下，将位置不符合的元素进行交换			if(1 <= value && value <= size && value != nums.at(value - 1))			{				swap(nums.at(i) ,nums.at(value - 1) );				//每次交换后，当前位置不一定符合，所以i--,再重新计算一次				i--;			}		}		//从头开始遍历		for(int i = 0 ; i < size ; i++)		{			if(nums.at(i) != (i + 1) )			{				return (i+1);			}		}		//如果数组中元素都符合摆放，则说明是最后一个元素，数组长度+1		return (size + 1);    }};void PRocess(){	Solution solution;	int num;	vector<int> nums;	int value;	while(cin >> num)	{		nums.clear();		for(int i = 0 ; i < num ; i++)		{			cin >> value;			nums.push_back(value);		}		int result = solution.firstMissingPositive(nums);		cout << result << endl;	}}int main(int argc , char* argv[]){	process();	getchar();	return 0;}