leetcode347.前K个高频元素

题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

解答

使用hashmap辅助

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> m; // 创建一个用于存储数字频率的映射（键为数字，值为出现的次数）
        for (int num : nums) {
            m[num] = m[num] == 0 ? 1 : m[num] + 1; // 统计每个数字的出现次数
        }
        vector<std::pair<int, int>> vec(m.begin(), m.end()); // 将映射转换为包含键值对的向量
        sort(vec.begin(), vec.end(), [](const std::pair<int, int>& a, const std::pair<int, int>& b) {
            return a.second > b.second; // 按值（出现次数）降序排序
        });
        vector<int> results;
        for (int i = 0; i < k; i++) {
            results.push_back(vec[i].first); // 获取前k个频率最高的数字
        }
        return results;
    }
};

代码优化

**使用 unordered_map 而不是 map**：unordered_map 通常比 map 更快，因为 unordered_map 使用哈希表实现，而 map 使用平衡树。这在频繁插入和查找时尤其有用。

简化元素计数：你可以直接使用 ++m[num] 来增加计数，无需检查元素是否存在。

使用优先队列（最小堆）：使用优先队列而不是对整个向量排序可以减少时间复杂度。只保留前 k 个最频繁的元素，这样不需要对所有元素进行排序。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 使用 unordered_map 来计数
        unordered_map<int, int> count_map;
        for (int num : nums) {
            ++count_map[num];
        }

        // 定义一个最小堆
        auto comp = [&count_map](int n1, int n2) {
            return count_map[n1] > count_map[n2];
        };
        priority_queue<int, vector<int>, decltype(comp)> heap(comp);

        // 保持堆的大小为 k
        for (auto &p : count_map) {
            heap.push(p.first);
            if (heap.size() > k) {
                heap.pop();
            }
        }

        // 从堆中提取元素
        vector<int> results;
        while (!heap.empty()) {
            results.push_back(heap.top());
            heap.pop();
        }
        reverse(results.begin(), results.end()); // 将结果反转为正确的顺序
        return results;
    }
};