找到数组中未出现的最小整数

野性酷女 2023-10-19 06:56 120阅读 0赞

【题目】: 给定一个无序整型数组arr，找到数组中未出现的最小正整数。要求时间复杂度为O(N)，空间复杂度为O(1)。

例如：

arr=\[-1,2,3,4\]。返回1。

arr=\[1,2,3,4\]。返回5。

【解法】  
一、穷举查找  
最小正整数是1，所以常规的方法就是在数组中找1，然后是2，依次找下去…。一直找到第一个没有出现的正整数，这个数就是未出现的最小的正整数。

for i = 1 to n

do if i not in A

then return i

return n+1  
  
显然，这里的算法复杂度是O(n^2)。

二、先排序再查找  
第一种方法，每次查找都是线性查找，要改进最先想到的自然是二分查找， 所以：  
先排序，用O(nlgn)的快速排序、归并排序或者堆排序；因为数组中的元素是一些自然数，我们甚至可以使用O(n) 的基数排序，当然，需要更多的内存。  
对1..n进行判断，复杂度也为O(nlgn)  
所以，整体的算法复杂度为O(nlgn)

三、利用这种数组的特性

先排序  
再利用该特性搜索  
for i = 1 to n

do if A\[i\] > i

then return i

return n+1  
  
注意到，如果我们使用基数排序，可以将复杂度降低到O(n)。  
（1） arr为整数1,2,3…N的一个随机排列，那个未出现的最小正整数就是N+1。

（2） arr中有小于1或者大于N的数出现(我们称之为“不合法”的数)，则未出现的最小正整数一定在1到N中间（因为数组一共只有N个数，如果出现不合法的数，则出现的1到N之间的数的个数一定小于N，故一定有没有出现的数）。

下面介绍一种判断一个数组中没有出现的最小正数的方法，要保证效率：

时间复杂度O(n)

空间复杂度O(1)

方法思路：使用数组下标，通过交换，保证数组下标为i的元素值为i+1，即arr\[i\]=i+1，然后从前往后，不满足此条件的数即为所求。

实现代码：  
//判断一个数组中没有出现的最小正数  
//时间复杂度O(n)，空间复杂度O(1)  
\#include <iostream>  
using namespace std;  
  
int del\_min\_positive(int \*data, int num)  
\{  
for(int i=0;i<num;++i)  
\{  
if(data\[i\]>=1&&data\[i\]<=num)  
\{  
swap(data\[i\],data\[data\[i\]-1\]);  
\}  
\}  
for(int i=0;i<num;++i)  
\{  
if(data\[i\]!=i+1)  
\{  
return i+1;  
\}  
\}  
return num+1;  
\}  
  
int main()  
\{  
int arr\[\]=\{0,2,3,4,2,5,-3,1\};  
cout<<del\_min\_positive(arr,sizeof(arr)/sizeof(int))<<endl;