347.前 K 个高频元素

原题地址

本题有多种方法，并且由于Python语言的特性，也有多种实现方式。

不过不外乎用哈希表+快排/堆排的方式来实现。

方法一 sorted()函数

sorted()函数内部实现为timsort

关于timsort

哈希表用字典形式存储，统计每个数字出现的个数。

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    nums_dic = dict()  # 哈希表，存储的是数字以及出现的次数
    for num in nums:
        if num not in nums_dic:
            nums_dic[num] = 1
        else:
            nums_dic[num] += 1
    # 将其排序，得到[(num1, count1), (num2, count2), ...]形式的列表
    nums_list = sorted(nums_dic.items(), key=lambda x:x[1],reverse=True)
    rel = []
    for i in range(k):
        rel.append(nums_list[i][0])
    return rel

上述哈希表的实现可以用collection.Counter()函数自动得到

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    nums_dic = collections.Counter(nums)
    # 将其排序，得到[(num1, count1), (num2, count2), ...]形式的列表
    nums_list = sorted(nums_dic.items(), key=lambda x:x[1],reverse=True)
    rel = []
    for i in range(k):
        rel.append(nums_list[i][0])
    return rel

方法二 most_common()函数

用python自带函数most_common()自动排序，并取前k个

注：most_common()内部实现是用的堆排序

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    nums_dic = collections.Counter(nums)
    return [item[0]  for item in nums_dic.most_common(k)]

方法三 快速排序(快速选择)

因为题目要求选出出现次数最多的k个，但是不需要按出现次数从大到小排列，所以我们可以用快速排序的思路，只要排好第k个元素，那么它前面的元素都是比它大的，它后面的都是比它小的，返回前k个，完毕。

此解法与215题解法几乎一致

215.数组中的第K个最大元素

def topKFrequent(self, nums: List[int], k: int) -> List[int]:
    def Partition(low, high):
        temp = nums_list[low]
        pivlot = nums_list[low][1]
        while low < high:
            while low < high and nums_list[high][1] <= pivlot:
                high -= 1
            nums_list[low] = nums_list[high]
            while low < high and nums_list[low][1] >= pivlot:
                low += 1
            nums_list[high] = nums_list[low]
        nums_list[low] = temp
        return low
    def quickSort(low, high):  # 对数组排序,找到第k大的数
        if low < high:
            pivlotpos = Partition(low, high)
            if pivlotpos == k:
                return None
            elif pivlotpos > k:
                quickSort(low, pivlotpos-1)
            else:
                quickSort(pivlotpos+1, high)
    nums_dic = collections.Counter(nums)
    nums_list = [(num, freq) for num, freq in nums_dic.items()]
    low, high = 0, len(nums_list)-1
    k -= 1  # 表示要寻找排序后下标为k的那个数
    quickSort(low, high)
    return [item[0] for item in nums_list[:k+1]]

c++版

class Solution {
public:
    int quickSort(vector<pair<int, int>>& v, int low, int high){
        int guard = v[low].second;
        pair<int, int> t = v[low];
        while(low < high) {
            while(low < high && v[high].second < guard)   high--;
            v[low] = v[high];
            while(low < high && v[low].second >= guard)   low++;
            v[high] = v[low];
        }
        v[low] = t;
        return low;
    }
    void mySort(vector<pair<int, int>>& v, int start, int end, int k){
        int pivotPos = quickSort(v, start, end);
        if(pivotPos == k-1)   return;
        else if(pivotPos > k-1)    mySort(v, start, pivotPos-1, k);
        else    mySort(v, pivotPos+1, end, k);
    }
    vector<int> topKFrequent(vector<int>& nums, int k) {
        map<int, int> m;
        for(auto num : nums){
            m[num]++;
        }
        vector<pair<int, int> > v(m.begin(), m.end());
        mySort(v, 0, v.size()-1, k);
        vector<int> ans;
        for(int i=0; i<k; i++)
            ans.push_back(v[i].first);
        return ans;
    }
};