leetcode347. Top K Frequent Elements

imccl 發(fā)布于2019-08-15 15:54 / 1172人閱讀

摘要：題目要求假設(shè)有一個非空的整數(shù)數(shù)組，從中獲得前個出現(xiàn)頻率最多的數(shù)字。先用來統(tǒng)計出現(xiàn)次數(shù)，然后將其丟到對應(yīng)的桶中，最后從最高的桶開始向低的桶逐個遍歷，取出前個頻率的數(shù)字。

題目要求

Given a non-empty array of integers, return the k most frequent elements.

For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note: 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm"s time complexity must be better than O(n log n), where n is the array"s size.

假設(shè)有一個非空的整數(shù)數(shù)組，從中獲得前k個出現(xiàn)頻率最多的數(shù)字。

思路和代碼

這里有一個額外要求即時間復(fù)雜度要優(yōu)于O(n log n)，也就是說我們無法采用先排序再順序計算的方式來進行統(tǒng)計，因為最好的排序算法其平均的時間復(fù)雜度也需要O(n log n)。那么有沒有別的方法可以讓我們達到更好的效率呢？

這里的核心思路是桶排序，我們通過使用n+1個桶（其中第i個桶代表出現(xiàn)i次的數(shù)據(jù)）來匯攏每個數(shù)字出現(xiàn)的次數(shù)。先用HashMap來統(tǒng)計出現(xiàn)次數(shù)，然后將其丟到對應(yīng)的桶中，最后從最高的桶開始向低的桶逐個遍歷，取出前k個頻率的數(shù)字。

    public List topKFrequent(int[] nums, int k) {
        List[] buckets = new List[nums.length + 1];
        Map frequency = new HashMap();
        
        for(int num : nums){
            frequency.put(num, frequency.getOrDefault(num, 0) + 1);
        }
        
        for(int key : frequency.keySet()){
            int frequencyOfKey = frequency.get(key);
            if(buckets[frequencyOfKey] == null){
                buckets[frequencyOfKey] = new ArrayList();
            }
            buckets[frequencyOfKey].add(key);
        }
        
        List result = new ArrayList();
        for(int i = buckets.length-1 ; i>=0 && k>result.size() ; i--){
            if(buckets[i] != null){
                result.addAll(buckets[i]);
            }
        }
        return result;
    }

想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號！將會不定期的發(fā)放福利哦~