347. Top K Frequent Elements

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.

一刷
题解:利用bucket sort的思路,先统计词频,然后再将frequency作为index访问得到具体的词。从大到小的前k个。

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {

    List<Integer>[] bucket = new List[nums.length + 1];
    Map<Integer, Integer> frequencyMap = new HashMap<Integer, Integer>();

    for (int n : nums) {
        frequencyMap.put(n, frequencyMap.getOrDefault(n, 0) + 1);
    }

    for (int key : frequencyMap.keySet()) {
        int frequency = frequencyMap.get(key);
        if (bucket[frequency] == null) {
            bucket[frequency] = new ArrayList<>();
        }
        bucket[frequency].add(key);
    }

    List<Integer> res = new ArrayList<>();

    for (int pos = bucket.length - 1; pos >= 0 && res.size() < k; pos--) {
        if (bucket[pos] != null) {
            res.addAll(bucket[pos]);
        }
    }
    return res;
}
}

二刷

class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        
        List<Integer> result = new ArrayList();
        
        if (nums.length == 0 || nums.length == 1){
            if(k == 1){
                result.add(nums[0]);
            }
            
            return result;
        }
        
        PriorityQueue<Node> pq = new PriorityQueue<Node>(k,new NodeComparator());
        Arrays.sort(nums);
        
        int count = 1 ;
        for (int i = 1; i< nums.length;i++){
            if (nums[i] != nums[i-1]){
                pq.add(new Node(nums[i-1],count));
                count = 1;
            }else{
                count++;
            }
            
        }
        
        pq.add(new Node(nums[nums.length-1],count));
        
        count = 0; 
        while(count++<k){
            result.add(pq.poll().key);
        }
        
        return result;
        
    }
}

class Node{
    int key;
    int count;
    
    Node(int key, int count){
        this.key = key;
        this.count = count;
    }
}

class NodeComparator implements Comparator<Node>{
    public int compare(Node a, Node b){
        if (a.count > b.count ){
            return -1;
        }else if (a.count < b.count){
            return 1;
        }else{
            return 0;
        }
    }
}
最后编辑于 :
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 13,163评论 0赞 33
  • **2014真题Directions:Read the following text. Choose the be...
    又是夜半惊坐起阅读 12,177评论 0赞 23
  • 最近刷了几部XX小说,对于社会和现实的理解似乎明朗了许多。 遗憾的是 十多年的圣贤书也没有教会我在现实中获得快速成...
    羊羊羊同学阅读 478评论 0赞 1
  • 昀靋 仲尼曾有己勿述 世人皆識藥言故 不若墨香繞指上 孤觀行間理自悟
    冷眼袋阅读 314评论 0赞 0

友情链接更多精彩内容