题目

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
进阶：你所设计算法的时间复杂度必须优于 O(n log n) ，其中 n 是数组大小。

示例：

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

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

解答 & 代码

解法一：哈希表 + 大根堆

class Solution {
private:
    struct cmp {
        bool operator() (vector<int> nums1, vector<int> nums2) {
            return nums1[1] < nums2[1];
        }
    };
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 哈希表，存储数值出现次数，key = 数值，val = 出现次数
        unordered_map<int, int> numCntMap;
        for(int i = 0; i < nums.size(); ++i)
            ++numCntMap[nums[i]];
        // 优先队列实现的大根堆，存储 vector<int>{数值，出现次数}, 并用出现次数来比较大小
        priority_queue<vector<int>, vector<vector<int>>, cmp> maxHeap;
        for(auto it = numCntMap.begin(); it != numCntMap.end(); ++it)
            maxHeap.push(vector<int>{it->first, it->second});
        // 大根堆依次弹出前 K 个元素，即为前 K 个高频元素
        vector<int> result;
        for(int i = 0; i < k; ++i)
        {
            int num = maxHeap.top()[0];
            maxHeap.pop();
            result.push_back(num);
        }
        return result;
    }
};

复杂度分析：设数组长度为 N，包含 M 种不同的数值

时间复杂度 O(M logM)：
- 遍历数组，将数值及其出现次数存入哈希表，时间复杂度 O(N)
- 遍历哈希表，将 M 个键值存入优先队列，时间复杂度 O(MlogM)
- 从优先队列中弹出前 K 个元素，时间复杂度 O(KlogM)
- 因此，总的时间复杂度 O(M logM)，满足题目要求的优于 O(N logN)
空间复杂度 O(M)：
- 哈希表和优先队列的最大长度都是 M
- 结果数组长为 K，不计

执行结果：

执行结果：通过
执行用时：36 ms, 在所有 C++ 提交中击败了 5.92% 的用户
内存消耗：15.7 MB, 在所有 C++ 提交中击败了 5.03% 的用户

解法二：哈希表 + 小根堆

由于题目只要求返回前 K 个高频元素，而不要求这 K 个元素按频次排序，因此可以用小根堆代替大根堆，这样堆中只需要存储 K 个元素，而不用存储全部 M 个键值，每次插入、删除的时间复杂度从 O(logM) 降为 O(logK)，最坏情况下 M 个键值对各插入、删除一次，总体时间复杂度从 O(M logM) 降为 O(M logK)

struct cmp {
    bool operator() (pair<int, int> pair1, pair<int, int> pair2)
    {
        return pair1.second > pair2.second;
    }
};
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 哈希表统计每个元素出现的次数，key = 元素数值，val = 出现次数
        unordered_map<int, int> numFreqMap;
        for(int i = 0; i < nums.size(); ++i)
            ++numFreqMap[nums[i]];
        // 优先队列（小根堆），维护前 k 个高频元素
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> minHeap;
        for(auto it = numFreqMap.begin(); it != numFreqMap.end(); ++it)
        {
            // 堆的元素个数小于 k 时，直接插入
            if(minHeap.size() < k)
                minHeap.push(make_pair(it->first, it->second));
            // 如果堆的元素个数等于 k，则比较堆顶和当前元素的大小，
            // 如果当前元素更大，则弹出堆顶，插入当前元素；否则不操作，舍弃当前元素
            else
            {
                if(it->second > minHeap.top().second)
                {
                    minHeap.pop();
                    minHeap.push(make_pair(it->first, it->second));
                }
            }
        }
        // 将堆中的 k 各元素弹出，存入结果数组并返回
        vector<int> result(k);
        for(int i = k - 1; i >= 0; --i)
        {
            result[i] = minHeap.top().first;
            minHeap.pop();
        }
        return result;
    }
};

复杂度分析：设数组长度为 N，包含 M 种不同的数值，题目要求返回前 K 个高频元素

时间复杂度 O(M logK)：
- 遍历数组，将数值及其出现次数存入哈希表，时间复杂度 O(N)
- 优先队列中只会有 K 个元素，因此每次插入、删除操作时间复杂度 O(logK)。而最坏情况下哈希表中每个键值对都会插入优先队列一次，删除一次，因此时间复杂度 O(M logK)
- 因此，总的时间复杂度 O(M logK)，满足题目要求的优于 O(N logN)
空间复杂度 O(M)：
- 哈希表最大长度是 M
- 小根堆的最大长度是 K
- 结果数组长为 K，不计

执行结果：

执行结果：通过
执行用时：28 ms, 在所有 C++ 提交中击败了 5.94% 的用户
内存消耗：15.6 MB, 在所有 C++ 提交中击败了 5.01% 的用户

解法三：哈希表 + 快速选择

class Solution {
private:
    // 快排分割函数
    int partition(vector<pair<int, int>>& arr, int left, int right)
    {
        int randomIdx = random() % (right - left + 1) + left;
        swap(arr[left], arr[randomIdx]);
        pair<int, int> pivot = arr[left];
        while(left < right)
        {
            while(left < right && arr[right].second <= pivot.second)
                --right;
            arr[left] = arr[right];
            while(left < right && arr[left].second >= pivot.second)
                ++left;
            arr[right] = arr[left];
        }
        arr[left] = pivot;
        return left;
    }
    // 快速选择：使得数组第 k 大的元素在第 k 个位置上（arr[k-1]），且前面的数都比它大，后面的数都比它小
    void quickSelect(vector<pair<int, int>>& arr, int left, int right, int k)
    {
        if(left >= right)
            return;
        int pivot = partition(arr, left, right);
        if(pivot == k - 1)
            return;
        else if(pivot < k - 1)
            quickSort(arr, pivot + 1, right, k);
        else
            quickSort(arr, left, pivot - 1, k);
    }
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // 哈希表，存储数值出现次数，key = 数值，val = 出现次数
        unordered_map<int, int> numCntMap;
        for(int i = 0; i < nums.size(); ++i)
            ++numCntMap[nums[i]];
        // 将哈希表中的键值对存入数组 arr，并进行快速选择
        vector<pair<int, int>> arr;
        for(auto it = numCntMap.begin(); it != numCntMap.end(); ++it)
            arr.push_back(make_pair(it->first, it->second));
        quickSelect(arr, 0, arr.size() - 1, k);
        // 将 arr 的前 k 个元素存入结果数组，并返回
        vector<int> result(k);
        for(int i = 0; i < k; ++i)
            result[i] = arr[i].first;
        return result;
    }
};

复杂度分析：设数组长度为 N，包含 M 种不同的数值，题目要求返回前 K 个高频元素

时间复杂度 O(N)：
- 遍历数组 nums，将数值及其出现次数存入哈希表，时间复杂度 O(N)
- 遍历哈希表，将哈希表中的键值对都存入数组 arr，时间复杂度 O(M)
- 对数组 arr 进行快速选择，平均时间复杂度 O(N)
- 遍历快速选择后的数组 arr 的前 k 个元素，存入结果数组，时间复杂度 O(K)
- 因此，总的时间复杂度 O(N)，满足题目要求的优于 O(N logN)
空间复杂度 O(M)：
- 哈希表最大长度是 M
- 数组 arr 长度 M
- 结果数组长为 K，不计

执行结果：

执行结果：通过
执行用时：12 ms, 在所有 C++ 提交中击败了 83.95% 的用户
内存消耗：13.2 MB, 在所有 C++ 提交中击败了 86.69% 的用户

hot 100

[中等] 347. 前 K 个高频元素

题目

解答 & 代码

解法一：哈希表 + 大根堆

解法二：哈希表 + 小根堆

解法三：哈希表 + 快速选择