当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数

题目描述

215 Kth Largest Element in an Array
https://leetcode-cn.com/problems/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.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

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


相似题目

LeetCode.215.Kth Largest Element in an Array 寻找数组中第K大的数
LeetCode.703.Kth Largest Element in a Stream 数据流中的第K大元素
LeetCode.347.Top K Frequent Elements 前K个高频元素
LeetCode.剑指offer.040.数组中最小的k个数
LeetCode.023.Merge k Sorted Lists 合并K个排序链表


解题过程

快速排序的应用

典型的 快速排序的应用,由于快排每次 partition 后枢轴的位置是最终固定的,我们只需要考察每次 partition 后枢轴的位置来决定接下来在哪个半边中搜索。

平均时间复杂度 O(n),最坏情况(数组已有序)下时间复杂度为 O(n^2),空间复杂度 O(1)

private static class SolutionV202002 {
    public int findKthLargest(int[] nums, int k) {
        int low = 0, high = nums.length -1;
        // 第k大的数在升序排序后数组中的下标
        int targetIndex = nums.length - k;
        int partition = partition(nums, low, high);
        while (partition != targetIndex) {
            if (partition < targetIndex) {
                low = partition + 1;
            } else {
                high = partition - 1;
            }
            partition = partition(nums, low, high);
        }
        return nums[partition];
    }

    // 一次快速排序partition,把nums中小于 nums[0] 的放左边,大于 nums[0] 的放右边
    private int partition(int[] nums, int low, int high) {
        if (null == nums || nums.length ==0) {
            return 0;
        }
        if (low == high) {
            return low;
        }
        // 选 nums[0] 当枢轴
        int pivot = nums[low];
        while (low < high) {
            while (low < high && nums[high] >= pivot) {
               high--;
            }
            nums[low] = nums[high];
            while (low < high && nums[low] <= pivot) {
                low++;
            }
            nums[high] = nums[low];
        }
        // 枢轴归位
        nums[low] = pivot;
        return low;
    }
}

最小堆(推荐)

建立一个长度为K的最小堆,用数组的前K个元素初始化,然后从第K+1个元素开始扫描数组,如果大于堆顶,则互换元素,并从上到下调整堆;如果小于堆顶,则继续读入下一个,这样最后最小堆里剩的就是最大的K个元素.
或者
建立一个最小堆,原数组所有元素依次放入堆中,如果某次入堆后堆中元素个数大于 k,则弹出堆顶,也就是始终保持堆中元素个数小于等于 k,则最后堆顶就是第 k 大的数。
时间复杂度 O(nlogk),空间复杂度 O(k)

private static class SolutionV202006 {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(); // 默认是最小堆
        for (int n : nums) {
            priorityQueue.offer(n);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        return priorityQueue.peek();
    }
}

大顶堆(不推荐)

维护一个容量为 n 的大顶堆,把所有元素依次放入堆中,最后把堆顶的 k-1 个元素弹出,也就是弹出前 k-1 大的数,则剩下的堆顶就是第 k 大值。

向大小为 n 的堆中添加元素的时间复杂度为 O(logn),重复 n 次,故总时间复杂度为 O(nlogn),空间复杂度 O(n)

所以,可以看出如果用最大堆解决,需要容量为数组长度的最大堆,当数据长度非常大时(比如几亿个数据中找top 10),空间开销非常大,所以不推荐用最大堆。

import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int len = nums.length;
        // 使用一个含有 len 个元素的最大堆,lambda 表达式应写成:(a, b) -> b - a
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(len, (a, b) -> b - a);
        for (int i = 0; i < len; i++) {
            maxHeap.add(nums[i]);
        }
        for (int i = 0; i < k - 1; i++) {
            maxHeap.poll();
        }
        return maxHeap.peek();
    }
}

GitHub代码

algorithms/leetcode/leetcode/_215_KthLargestElementInArray.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_215_KthLargestElementInArray.java


上一篇 LeetCode.234.Palindrome Linked List 判断是否回文单链表

下一篇 Elasticsearch

阅读
评论
924
阅读预计4分钟
创建日期 2020-02-20
修改日期 2020-06-29
类别

页面信息

location:
protocol:
host:
hostname:
origin:
pathname:
href:
document:
referrer:
navigator:
platform:
userAgent:

评论