给定一个含个整数的数组,请设计一个在时间上尽可能高效的算法,找出数组中未出现的最小正整数。给出完整能运行的c++代码。例如,数组{-5,3,2,3}中未出现的最小正整数是1;数组{1,2,3}中未出现的最小正整数是4.
时间: 2024-10-09 08:01:54 浏览: 30
为了找到一个整数数组中未出现的最小正整数,可以使用哈希集合(unordered_set)的数据结构。这个数据结构提供常数时间复杂度的查找和插入操作,非常适合这样的场景。以下是用C++实现的一个高效算法:
```cpp
#include <iostream>
#include <unordered_set>
int findMissingPositive(const std::vector<int>& nums) {
std::unordered_set<int> hashSet;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (nums[i] > 0 && nums[i] <= n) {
// 如果元素在合法范围内,则从列表中移除
hashSet.erase(nums[i]);
}
}
// 从1开始检查,因为这是第一个可能出现的正整数
for (int i = 1; ; ++i) {
// 如果不在集合中,返回该数字
if (hashSet.count(i) == 0) {
return i;
}
}
}
int main() {
std::vector<int> nums = {-5, 3, 2, 3};
std::cout << "未出现的最小正整数是: " << findMissingPositive(nums) << std::endl;
nums = {1, 2, 3};
std::cout << "未出现的最小正整数是: " << findMissingPositive(nums) << std endl;
return 0;
}
```
在这个算法中,首先遍历输入数组,将范围内的正整数从哈希集合中移除。然后,从1开始逐个检查剩余的正整数是否出现在集合中,找到的第一个不在集合中的数就是我们要找的未出现的最小正整数。
阅读全文