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

题目

在未排序的数组中找到第 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