[LintCode] Top k Largest Numbers I

solocoder 发布于2019-08-15 13:25 / 701人阅读

Problem

Given an integer array, find the top k largest numbers in it.

Example

Given [3,10,1000,-99,4,100] and k = 3.
Return [1000, 100, 10].

Tags

Heap Priority Queue

Solution

public class Solution {
    public int[] topk(int[] nums, int k) {
 
        //construct comparator, then priority-queue
        Comparator comparator = new Comparator() {
            public int compare(Integer v1, Integer v2) {
                //can also use `return v2-v1;`
                if (v1 < v2) {
                    return 1;
                } else if (v1 > v2) {
                    return -1;
                } else {
                    return 0;
                }
            }
        };
        
        PriorityQueue maxHeap = new PriorityQueue<>(k, comparator);
        
        //use maxHeap to get top k largest
        for (int num: nums) {
            maxHeap.offer(num);
        }
        
        //save to res array
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = maxHeap.poll();
        }
        
        return res;
    }
}

云服务器 GPU云服务器 Largest Numbers LintCode LintCode134_LRU

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

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

[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
[LeetCode/LintCode] Largest Palindrome Product

Problem Find the largest palindrome made from the product of two n-digit numbers. Since the result could be very large, you should return the largest palindrome mod 1337. Example Input: 2Output: 987Ex...

Barry_Ng 2019-08-15 18:16 评论0 收藏0
[LintCode] Print Numbers by Recursion

摘要：只有当位数时，才打印数字。首先分析边界，应该，然后用存最高位。用函数对进行递归运算，同时更新结果数组。更新的过程归纳一下，首先，计算最高位存入，然后，用到倍的和之前里已经存入的所有的数个循环相加，再存入，更新，计算更高位直到等于 Problem Print numbers from 1 to the largest number with N digits by recursion. ...

kumfo 2019-08-14 15:17 评论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
[LintCode/LeetCode] Check Sum of K Primes

Problem Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers. Example Given n = 10, k = 2Return true // 10 = 5 + 5 Given n = 2, k = 2Return false Solution pub...

lakeside 2019-08-16 12:37 评论0 收藏0