有一个含n（n<100）个整数的无序序列R，设计一个算法，从小到大顺序求前k（1≤k≤n）个最大的元素。 C++

要设计一个算法，从小到大顺序求前k个最大的元素，可以使用多种方法。这里介绍一种时间复杂度较低的方法，即使用最小堆（Min Heap）。 ### 算法步骤： 1. **构建最小堆**：从无序序列R中取出前k个元素，构建一个最小堆。这个最小堆的堆顶元素是当前k个元素中最小的。 2. **遍历剩余元素**：从第k+1个元素开始遍历序列R。对于每个元素，如果它大于堆顶元素，则将其替换堆顶元素，并调整堆使其重新成为最小堆。 3. **获取结果**：最终，最小堆中的k个元素就是序列R中前k个最大的元素。 ### C++代码实现： ```cpp #include <iostream> #include <vector> #include <algorithm> // 调整堆，使其成为最小堆 void minHeapify(std::vector<int>& heap, int index, int heapSize) { int smallest = index; int left = 2 * index + 1; int right = 2 * index + 2; if (left < heapSize && heap[left] < heap[smallest]) { smallest = left; } if (right < heapSize && heap[right] < heap[smallest]) { smallest = right; } if (smallest != index) { std::swap(heap[index], heap[smallest]); minHeapify(heap, smallest, heapSize); } } // 构建最小堆 void buildMinHeap(std::vector<int>& heap) { int heapSize = heap.size(); for (int i = heapSize / 2 - 1; i >= 0; --i) { minHeapify(heap, i, heapSize); } } // 获取前k个最大的元素 std::vector<int> getTopK(const std::vector<int>& R, int k) { std::vector<int> heap(R.begin(), R.begin() + k); buildMinHeap(heap); for (int i = k; i < R.size(); ++i) { if (R[i] > heap[0]) { heap[0] = R[i]; minHeapify(heap, 0, k); } } return heap; } int main() { std::vector<int> R = {3, 1, 6, 8, 2, 9, 4, 5, 7}; int k = 4; std::vector<int> topK = getTopK(R, k); std::cout << "前" << k << "个最大的元素是: "; for (int num : topK) { std::cout << num << " "; } std::cout << std::endl; return 0; } ``` ### 代码解释： 1. `minHeapify`函数：用于调整堆，使其成为最小堆。 2. `buildMinHeap`函数：构建最小堆。 3. `getTopK`函数：获取前k个最大的元素。 4. `main`函数：测试代码，输出前k个最大的元素。