[C++知识库]LeetCode347. 前K个高频元素（排序实现）

题目链接 前K个高频元素

这道题从排序的角度去理解得话，可以看作第56题：“合并区间”和第57题：“数组中第K个最大元素”的一个组合，基本的思路是先将容器nums通过最大堆排序，然后建立一个二维容器存放各个不同数字的值和出现次数，最后再输出出来。

我的题解

class Solution {
public:
    //下滤函数
    void PercDowm(vector<int>& v, int p, int N)
    {
        int X{ v[p] };
        int Parent, Chirld;
        for (Parent = p; Parent * 2 + 1 < N; Parent = Chirld) {
            Chirld = Parent * 2 + 1;
            if (Chirld != N -1 && v[Chirld] < v[Chirld + 1])
                ++Chirld;
            if (X >= v[Chirld])
                break;
            else {
                v[Parent] = v[Chirld];
            }
        }
        v[Parent] = X;
    }

    void HeapSort(vector<int>& v)
    {
        //建立最大堆
        for (int i = v.size() / 2 - 1; i >= 0; --i) {
            PercDowm(v, i, v.size());
        }

        //“删除”（排序）操作
        for (int i = v.size() - 1; i > 0; --i) {
            swap(v[0], v[i]);
            PercDowm(v, 0, i);
        }
    }

        vector<int> topKFrequent(vector<int>& nums, int k) {
        HeapSort(nums);
        vector<vector<int>> answer{};//存放元素值和元素出现次数的二维容器
		vector<int> temp_answer(2,0);
        temp_answer[0] = 1; temp_answer[1] = nums[0];
        answer.push_back(temp_answer);
        for (int i = 1; i < nums.size(); ++i) {
            if (answer.back()[1] != nums[i]) {
                temp_answer[0] = 1; temp_answer[1] = nums[i];
                answer.push_back(temp_answer);
            }
            else {
                ++answer.back()[0];
            }
        }
        sort(answer.begin(), answer.end());
        vector<int> last_answer{};//最终答案
        for (int i = 1; i <= k; ++i) {
            last_answer.push_back(answer[answer.size() - i][1]);
        }
        return last_answer;
    }
};