给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数

数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数"/>

给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数

分析： 题中要求算法有尽可能高的时间复杂度，即可采用空间换时间的方法。
分析： 假设数组A为题中所给，则可以构造一个含有n个数据元素的数组B(即保持数组B和所给数组A大小相同)，并把数组B中所有元素设置为0，接下来循环遍历数组A,若A中的数据元素大于0并且小于n,则把数组B中对应元素由0设置为1，直到循环结束。接下来循环遍历数组B，找出数组B中第一个数据元素为0的位置(此时该位置为所求的最小正整数的元素值-1)，返回该位置+1即为所求的最小正整数。
注:此算法的核心思想就是以数组A中的元素值为地址映射到数组B中。
代码如下:
1.该算法的代码:

int findInteger(vector<int> &A)//算法实现
{int n=A.size();int B[n];//声明一个数组B，与数组A所含元素个数相同for(int i=0;i<n;i++)//把数组B中所有元素设置为0{B[i]=0;}for(int i=0;i<A.size();i++)//把A中的元素按照地址映射存进到B中{if(A[i]>0 && A[i]<n){B[A[i]-1]=1;}}for(int i=0;i<n;i++)//查找B中元素，返回第一个值为0的数组元素位置(该位置同时也是所找最小正整数的值-1){if(B[i]==0) return i+1;}
}

2.整个程序实现代码:

#include<iostream>
#include<vector>
using namespace std;
vector<int>array;
int findInteger(vector<int> &A)//算法实现
{int n=A.size();int B[n];//声明一个数组B，与数组A所含元素个数相同for(int i=0;i<n;i++)//把数组B中所有元素设置为0{B[i]=0;}for(int i=0;i<A.size();i++)//把A中的元素按照地址映射存进到B中{if(A[i]>0 && A[i]<n){B[A[i]-1]=1;}}for(int i=0;i<n;i++)//查找B中元素，返回第一个值为0的数组元素位置(该位置同时也是所找最小正整数的值-1){if(B[i]==0) return i+1;}
}int main()
{int a;cout<<"请依次向该数组输入整数元素:";while (cin>>a){array.push_back(a);if(cin.get()=='\n') break;}cout<<"您输入了"<<array.size()<<"个整数,"<<"分别为:";for(int i=0;i<array.size();i++){cout<<array[i]<<" ";}cout<<endl;cout<<"未出现的最小正整数为"<<findInteger(array)<<endl;return 0;
}

3.运行结果如下: