给定一个含n(n>1)个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是。用c语言实现
时间: 2024-05-09 12:17:18 浏览: 63
一个未排序的整数数组,请找出其中没有出现的最小的正整数。
5星 · 资源好评率100%
好的,我明白了。对于您的问题,我可以提供以下C语言代码实现:
```
int findMissingNum(int arr[], int n) {
int i, j;
// 过滤掉所有非正数
for(i = 0; i < n; i++) {
if (arr[i] <= 0) {
arr[i] = INT_MAX;
}
}
// 标记数组中存在的正整数
for(i = 0; i < n; i++) {
if (abs(arr[i]) <= n) {
if (arr[abs(arr[i])-1] > 0) {
arr[abs(arr[i])-1] = -arr[abs(arr[i])-1];
}
}
}
// 返回第一个没被标记的数
for(i = 0; i < n; i++) {
if (arr[i] > 0) {
return i+1;
}
}
// 如果1到n都出现了,返回n+1
return n+1;
}
```
这个算法的思路是,对于n个整数至少有一个未出现的最小正整数不超过n+1,因此我们可以快速过滤掉所有非正数以及大于n+1的数,然后标记数组中已出现的正整数,最后在未被标记的数中找到最小的正整数即可。
使用时,您只需要在调用函数时传入数组和数组的长度即可,例如:
```
int main() {
int arr[] = {-5, 3, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
int missing = findMissingNum(arr, n);
printf("未出现的最小正整数为:%d\n", missing);
return 0;
}
```
输出结果为:未出现的最小正整数为:1
希望能够对您有所帮助。
阅读全文