剑指 Offer 40. 最小的k个数


剑指 Offer 40. 最小的 k 个数

常规法

public int[] getLeastNumbers(int[] arr, int k) {
        int[] vec = new int[k];
        Arrays.sort(arr);
        for (int i = 0; i < k; ++i) &#123;
            vec[i] = arr[i];
        &#125;
        return vec;
    &#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/

class Solution &#123;
    public int[] getLeastNumbers(int[] arr, int k) &#123;
        int[] vec = new int[k];
        if (k == 0) &#123; // 排除 0 的情况
            return vec;
        &#125;
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() &#123;
            public int compare(Integer num1, Integer num2) &#123;
                return num2 - num1;
            &#125;
        &#125;);
        for (int i = 0; i < k; ++i) &#123;
            queue.offer(arr[i]);
        &#125;
        for (int i = k; i < arr.length; ++i) &#123;
            if (queue.peek() > arr[i]) &#123;
                queue.poll();
                queue.offer(arr[i]);
            &#125;
        &#125;
        for (int i = 0; i < k; ++i) &#123;
            vec[i] = queue.poll();
        &#125;
        return vec;
    &#125;
&#125;

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
class Solution &#123;
    public int[] getLeastNumbers(int[] arr, int k) &#123;

        if (k == 0) &#123;
            return new int[0];
        &#125;
        // 使用一个最大堆(大顶堆)
        // Java 的 PriorityQueue 默认是小顶堆,添加 comparator 参数使其变成最大堆
        Queue<Integer> heap = new PriorityQueue<>(k, (i1, i2) -> Integer.compare(i2, i1));

        for (int e : arr) &#123;
            // 当前数字小于堆顶元素才会入堆
            if (heap.isEmpty() || heap.size() < k || e < heap.peek()) &#123;
                heap.offer(e);
            &#125;
            if (heap.size() > k) &#123;
                heap.poll(); // 删除堆顶最大元素
            &#125;
        &#125;

        // 将堆中的元素存入数组
        int[] res = new int[heap.size()];
        int j = 0;
        for (int e : heap) &#123;
            res[j++] = e;
        &#125;
        return res;
    &#125;

// 作者:nettee
// 链接:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/tu-jie-top-k-wen-ti-de-liang-chong-jie-fa-you-lie-/

&#125;

_Arrays.sort() _

时间复杂度 n_log_n
_
堆,时间复杂度  O(nlog⁡k)。


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
215. 数组中的第K个最大元素 215. 数组中的第K个最大元素
215. 数组中的第 K 个最大元素class Solution &#123; public int findKthLargest(int[] nums, int k) &#123; int heap
2021-02-26 future
下一篇 
剑指 Offer 10- I. 斐波那契数列 剑指 Offer 10- I. 斐波那契数列
剑指 Offer 10- I. 斐波那契数列写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:F(0) = 0,   F(1) = 1F(N) = F(N - 1) + F(N
2021-02-26 future
  目录