2025年求数组中未出现的最小正整数

科技前沿 • 2025-03-04 15:14 • 阅读 64

大家好，我是讯享网，很高兴认识大家。

【题目】: 给定一个无序整型数组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)。

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

int missMinNum(int arr[]) { int l = 0; //l表示已经从1到L已经出现（左边界），l的初值为0。 int r = arr.length; //如果一个数字过大（不合法），就会被扔掉，用r表示这个右边界，r初始值为arr长度。 // int temp; while(l < r) { if(arr[l] == l +1) { l++; } else if(arr[l]> r || arr[l] <= l || arr[arr[l] - 1] == arr[l])//不合法 { arr[l] =arr[--r]; } else//合法但是没有在理想的位置上 { temp = arr[l]; arr[l] =arr[arr[l] - 1]; arr[temp - 1] = temp; } } return l + 1; }

2025年求数组中未出现的最小正整数

相关推荐