leetcode347. Top K Frequent Elements

imccl 發布于2019-08-15 15:54 / 1166人閱讀

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

題目要求

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.

假設有一個非空的整數數組，從中獲得前k個出現頻率最多的數字。

思路和代碼

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

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

    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;
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Frequent Elements Leetcod LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69314.html

LeetCode 347. Top K Frequent Elements

摘要：描述給定一個非空的整數數組，返回其中出現頻率前高的元素。然后以元素出現的次數為值，統計該次數下出現的所有的元素。從最大次數遍歷到次，若該次數下有元素出現，提取該次數下的所有元素到結果數組中，知道提取到個元素為止。 Description Given a non-empty array of integers, return the k most frequent elements. E...

elva 2019-07-31 10:16 評論0 收藏0
[LeetCode] Top K Frequent Elements

Problem Given a non-empty array of integers, return the k most frequent elements. 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 e...

jkyin 2019-08-14 15:45 評論0 收藏0
[LeetCode] Top K Frequent Elements [HashMap/Heap/T

摘要：先按照元素次數的將所有元素存入，再按照次數元素將哈希表里的所有元素存入，然后取最后的個元素返回。 Problem 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: ...

AaronYuan 2019-08-14 15:56 評論0 收藏0
[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 評論0 收藏0
程序員進階之算法練習：LeetCode專場

摘要：例如題目解析題目的意思很明顯，就是把兩個數字加起來，需要考慮進位的情況。總結這個題目如果都能獨立完成，那么水平已經可以足以應付國內各大企業的算法面。歡迎大家前往騰訊云+社區，獲取更多騰訊海量技術實踐干貨哦~ 本文由落影發表前言 LeetCode上的題目是大公司面試常見的算法題，今天的目標是拿下5道算法題：題目1是基于鏈表的大數加法，既考察基本數據結構的了解，又考察在處理加法過程中...

MrZONT 2019-08-23 13:42 評論0 收藏0