#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.分析：尋找首次丟失的整數(shù)，但是給定的數(shù)組可能含有0和負數(shù)。題目只能用O(n)時間，不能排序。應(yīng)該是掃描一遍數(shù)組就算出答案。可以將不斷掃描的數(shù)進行異或處理：比如: 1^2=3      1^3^4=0001 ^ 0011 ^ 0100 = 0010^0100=0110=6	  和1^2^3^4=0110^0010=0100=4也就是說可以將數(shù)組中整數(shù)進行異或處理得到sum1，獲取數(shù)組中最大整數(shù)n,對1到n也異或處理得到sum2，將sum1與sum2進行異或處理，得到的結(jié)果如果為0，那么丟失的數(shù)為n+1;否則，丟失的整數(shù)為sum1^sum2未能求解出輸入:3(數(shù)組元素個數(shù))1 2 0(數(shù)組所有元素)43 4 -1 121 121000 -121 2輸出32213關(guān)鍵:1 解法：設(shè)定一種映射A[i] = i + 1,比如1對應(yīng)A[0]。如果找到某個元素A[i]，就將它和A[ A[i] -1 ]交換。        找到i從0開始找到第一個A[i] != i + 1的元素即可	//交換，在數(shù)組長度允許的條件下，將位置不符合的元素進行交換	if(1 <= value && value <= size && value != nums.at(value - 1))	{		swap(nums.at(i) ,nums.at(value - 1) );		//每次交換后，當(dāng)前位置不一定符合，所以i--,再重新計算一次		i--;	}2 		//如果是空數(shù)組，返回1，等于丟失第一個整數(shù)		if(nums.empty())		{			return 1;		}3 如果數(shù)組中出現(xiàn)重復(fù)元素需要規(guī)避4 并不一定是最大數(shù)之前的元素都會出現(xiàn)*/class Solution {public:    int firstMissingPositive(vector<int>& nums) {		//如果是空數(shù)組，返回1，等于丟失第一個整數(shù)		if(nums.empty())		{			return 1;		}		int size = nums.size();		//防止出現(xiàn)重復(fù)元素		int value;		for(int i = 0 ; i < size ; i++)		{			//元素i+1在下標(biāo)為i的位置上，則跳過			if(nums.at(i) == i + 1)			{				continue;			}			value = nums.at(i);			//交換，在數(shù)組長度允許的條件下，將位置不符合的元素進行交換			if(1 <= value && value <= size && value != nums.at(value - 1))			{				swap(nums.at(i) ,nums.at(value - 1) );				//每次交換后，當(dāng)前位置不一定符合，所以i--,再重新計算一次				i--;			}		}		//從頭開始遍歷		for(int i = 0 ; i < size ; i++)		{			if(nums.at(i) != (i + 1) )			{				return (i+1);			}		}		//如果數(shù)組中元素都符合擺放，則說明是最后一個元素，數(shù)組長度+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;}