题目地址: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; } } } };