【leetcode】347. Top K Frequent Elements

题目地址：https://leetcode.com/problems/top-k-frequent-elements/

从一个数组中求解出现次数最多的k个元素，本质是top k问题，用堆排序解决。

关于堆排序，其时间复杂度在最好和最坏的场景下都是O（nlogn）。

一开始想定义一个结构体，包含元素和元素个数两个成员，后直接用pair存储即可。

解题思路：

1. 分别统计每个数字的个数，建立数字和个数的映射，用pair存储，first=数字个数，second=数字，然后存入集合。

2. 以不同数字的个数建立大顶堆。

3.调整K次堆，依次得到K个出现次数最多的数字。

代码：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> topK;
        if (nums.size() == 0) {
            return topK;
        }
        vector<pair<int, int>> numVec;
        map<int, int> numMap;
        for(int num : nums) {
            if (numMap.count(num)) {
                numMap[num]++;
            } else {
                numMap[num] = 1;
            }
        }
        
        map<int, int>::iterator iter;
        iter = numMap.begin();
        while(iter != numMap.end()) {
            numVec.push_back(pair<int, int>(iter->second, iter->first));
            iter++;
        }
        int length = (int) numVec.size();
        for (int i = length / 2 - 1; i >= 0; i --) {
            sift(i, length - 1, numVec);
        }

        for (int i = length - 1; i > length - k - 1;  i --) {
            topK.push_back(numVec[0].second);
            swap(numVec[0], numVec[i]);
            sift(0, i - 1, numVec);
        }
        
        return topK;
    }
    
    void sift(int low, int high, vector<pair<int, int>> &numVec) {
        int i = low, j = 2 * i + 1;
        while (j <= high) {
            if (j < high && numVec[j].first < numVec[j+1].first) {
                j++;
            }
            
            if (numVec[i].first < numVec[j].first) {
                swap(numVec[i], numVec[j]);
                i = j;
                j = 2 * i + 1;
            } else {
                break;
            }
        }
    }

};