Kth Largest Element in an Array，Top K Frequent Ele

Tony_Zby 发布于2019-08-16 10:27 / 1412人阅读

摘要：解题思路，默认就是队列顶端是最小元素，第大元素，我们只要限制的大小为即可，最后队列顶端的就是第大元素。代码解题思路利用存入，之后采用，并限制最多放个元素。

Kth Largest Element in an Array
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

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

Note:
You may assume k is always valid, 1 ≤ k ≤ array"s length.

1.解题思路
PriorityQueue，默认就是队列顶端是最小元素，第k大元素，我们只要限制queue的大小为k即可，最后队列顶端的就是第k大元素。
2.代码

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums.length==0) return -1;
        PriorityQueue pq=new PriorityQueue();
        for(int i=0;ipq.peek()){
                pq.poll();
                pq.add(nums[i]);
            }
        }
        return pq.peek();
    }
}

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.

1.解题思路

利用HashMap存入，之后采用PriorityQueue，并限制最多放k个元素。

2.代码

public class Solution {
    public List topKFrequent(int[] nums, int k) {
        List res=new ArrayList();
        if(nums.length==0) return res;
        Map map=new HashMap();//
        for(int i=0;i> pq=new PriorityQueue>(new Comparator>(){
            public int compare(Map.Entry a,Map.Entry b){
                return a.getValue()-b.getValue();
            }
        
            });
       for(Map.Entry entry:map.entrySet()){
           pq.add(entry);
           if(pq.size()>k)
            pq.poll();
       }     
       while(pq.size()>0){
          Map.Entry entry=pq.poll();
          res.add(0,entry.getKey());
       } 
       return res;
    }
}

云服务器 GPU云服务器 in_array() in_array in_array()函数 in_array()示例代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69824.html

[Leetcode] Kth Largest Element in an Array 数组中第K大元

摘要：优先队列复杂度时间空间思路遍历数组时将数字加入优先队列堆，一旦堆的大小大于就将堆顶元素去除，确保堆的大小为。如果这个分界点是，说明分界点的数就是第个数。 Kth Largest Element in an Array Find the kth largest element in an unsorted array. Note that it is the kth largest e...

Rocko 2019-08-14 12:26 评论0 收藏0
[LintCode] Kth Largest Element [PriorityQueue]

摘要：可以不要用太简单的方法。先把它装满，再和队列顶端的数字比较，大的就替换掉，小的就。遍历完所有元素之后，顶部的数就是第大的数。 Problem Find K-th largest element in an array. Example In array [9,3,2,4,8], the 3rd largest element is 4.In array [1,2,3,4,5], the...

Hwg 2019-08-14 15:12 评论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
python 数据结构

python 数据结构 map # init map_ = {} map_ = {shiyang: 0, heanni: 1, china: 2} # existence print shiyang in map_ # add print map_[shiyang] # delete map_.pop(shiyang) #traverse for k in map_.keys(): pr...

Faremax 2019-07-25 11:32 评论0 收藏0
[LintCode] Top k Largest Numbers II

Problem Implement a data structure, provide two interfaces: add(number). Add a new number in the data structure.topk(). Return the top k largest numbers in this data structure. k is given when we crea...

jindong 2019-08-15 14:23 评论0 收藏0