利用c++实现以下代码并输出:给定一个含个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4.
时间: 2024-10-06 10:04:28 浏览: 31
delete--number.rar_K._delete namber_delete number_给定n位正整数
5星 · 资源好评率100%
要找到一个整数数组中未出现的最小正整数,可以使用哈希集合(unordered_set)来跟踪已经出现过的数字。遍历数组的同时将每个元素添加到哈希集合中。然后,从1开始遍历,检查每个正整数是否在集合中,如果没有就在结果中返回。
以下是使用C++实现这个算法的代码:
```cpp
#include <iostream>
#include <vector>
#include <unordered_set>
int findMissingPositiveNumber(std::vector<int>& nums) {
std::unordered_set<int> seen;
// 遍历数组并移除负数和0
for (int num : nums) {
if (num > 0) {
seen.insert(num);
}
}
int i = 1;
while (seen.find(i) == seen.end()) { // 当i不在集合中时,找到了缺失的正整数
return i++;
}
// 如果数组包含所有正整数直到某个点,那么下一个缺失的就是它们的最大值加一
return *std::max_element(nums.begin(), nums.end()) + 1;
}
int main() {
std::vector<int> nums = {-5, 3, 2, 3};
int missingNum = findMissingPositiveNumber(nums);
std::cout << "The missing positive number is: " << missingNum << std::endl;
return 0;
}
```
当运行此代码,对于输入数组{-5, 3, 2, 3},它将输出1,因为1是未出现的最小正整数。
阅读全文