#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)時間，不能排序。應該是掃描一遍數組就算出答案?？梢詫⒉粩鄴呙璧臄颠M行異或處理：比如: 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;}