求最小值和次最小值C加加
时间: 2024-09-08 13:03:35 浏览: 38
在C++中,求一组数中的最小值和次小值通常需要使用优先队列(堆)数据结构或者自定义排序算法。这里介绍两种常见的方法:
1. **堆实现**:
- 使用大顶堆(`std::priority_queue`),可以快速获取最小值。创建两个堆,一个存放所有元素,另一个只存放当前已找到的第二小的元素(初始化为最大值)。每次取出堆顶元素(即最小值)后,如果堆非空,则将新的最小值替换第二个堆的元素,然后继续从第一个堆中弹出元素直到堆为空。
```cpp
#include <queue>
int secondMin(vector<int>& nums) {
if (nums.empty()) return INT_MAX;
priority_queue<int> minHeap;
for (int num : nums) {
minHeap.push(num);
if (!minHeap.empty() && minHeap.top() != num) {
// 如果不是最大值,取出并保存第二小值
int secondMin = minHeap.top();
minHeap.pop();
minHeap.push(secondMin); // 保持最小堆性质
}
}
return minHeap.top(); // 返回次小值
}
```
2. **排序实现**:
- 首先对数组进行排序,然后直接返回第二大的元素。注意由于数组排序时间复杂度通常是O(n log n),这种方法对于大规模数据效率较低。
```cpp
#include <algorithm>
int secondMin(vector<int>& nums) {
sort(nums.begin(), nums.end());
if (nums.size() < 2) return INT_MAX; // 没有次小值
return nums[nums.size() - 2];
}
```