求第一个缺失的整数问题：
给定一个数组A[0...N-1]，找到从1开始，第一个不在数组中的正整数。
例如：3，5，1，2，-3，7，14，8；返回： 4。
问题分析：
可以将找到的数放在正确的位置上，如果最终发现某个元素一直没有找到，则该元素即为所求。
假设前 i-1 个数已经找到，并已经正确存放在前 i-1 位。则可以分下面几种情况：
- A[i] = i, i++;
- 1<A[i]<i, 丢弃；
- i<A[i]<N, 当A[i] = A[A[i]], 丢弃；当不等于的时候，交换；
- A[i]>N, 丢弃。
程序实现：
1 /*************************************** 2 FileName FindFirstMissingNum.cpp 3 Author : godfrey 4 CreatedTime : 2016/5/3 5 ****************************************/ 6 #include <iostream> 7 #include <cstring> 8 #include <vector> 9 #include <algorithm> 10 #include <stdio.h> 11 #include <stdlib.h> 12 13 using namespace std; 14 15 int FindFirstMissingNum(int* A,int size){ 16 int i = 1; 17 A --; 18 while(i<=size){ 19 if(A[i] == i){ 20 i++; 21 } 22 else if((A[i] < i) || (A[i] > size) || (A[i] == A[A[i]])){ 23 A[i] = A[size]; 24 size --; 25 } 26 else{ // if(A[i] > i) 27 swap(A[i],A[A[i]]); 28 } 29 } 30 return i; 31 } 32 int main() 33 { 34 int a[] = {3,5,1,2,-3,7,14,8}; 35 int FirstMissingNum = FindFirstMissingNum(a,sizeof(a)/sizeof(int)); 36 cout<<"the FirstMissingNum: "; 37 cout<<FirstMissingNum<<endl; 38 return 0; 39 }
运行结果：
转载请注明出处：
C++博客园：godfrey_88