算法:数组中的第 K 个最大元素

算法 大约 1277 字

题目

在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

可以假设k总是有效的,且1 ≤ k ≤ array.length

示例一

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例二

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

思路

数组排序后取第array.length - k个。

实现

方法一

冒泡排序:增加计数count,当排了k次序后,已经末尾k个元素已经有序,直接跳出循环,取末尾第k个;增加标志位flag,当轮询一次后都没有发生元素交换,说明已经有序,直接跳出循环,取末尾第k个。

public int findKthLargest(int[] arr, int k) {
    int count = 0;
    for (int i = 0; i < arr.length; i++) {
        boolean flag = false;
        for (int j = 0; j < arr.length - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                flag = true;
            }
        }
        // 一次都没交换,说明已经有序
        if (!flag) {
            break;
        }
        // 第k次排序后,末尾的几个元素已经有序
        count++;
        if (count >= k) {
            break;
        }
    }
    return arr[arr.length - k];
}

执行用时:49 ms, 在所有Java提交中击败了5.68%的用户

内存消耗:38.9 MB, 在所有Java提交中击败了26.97%的用户

方法二

直接调用Java工具类。- -!

public int findKthLargest(int[] arr, int k) {
    Arrays.sort(arr);
    return arr[arr.length - k];
}

执行用时:2 ms, 在所有Java提交中击败了90.42%的用户

内存消耗:38.7 MB, 在所有Java提交中击败了71.80%的用户

LeetCode 原题地址

https://leetcode-cn.com/problems/kth-largest-element-in-an-array

阅读 20 · 发布于 2021-02-23

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批