本文共 2498 字，大约阅读时间需要 8 分钟。

������������������������K������������������������������������������������������������������������������������������������������������

���������������������

���������������

class Solution {    public int findKthLargest(int[] nums, int k) {        if (nums == null || nums.length == 0) {            return -1;        }        int low = 0;        int high = nums.length - 1;        return findKth(nums, low, high, k);    }    public int findKth(int[] a, int low, int high, int k) {        int part = partition(a, low, high);        if (k == part - low + 1) {            return a[part];        } else if (k > part - low + 1) {            return findKth(a, part + 1, high, k - (part - part + 1));        } else {            return findKth(a, low, part - 1, k);        }    }    public int partition(int[] a, int low, int high) {        int key = a[low];        while (low < high) {            while (low < high && a[high] <= key) {                high--;            }            if (low == high) break;            a[low] = a[high];            while (low < high && a[low] >= key) {                low++;            }            a[high] = a[low];        }        a[low] = key;        return low;    }}

������������

• findKthLargest���������������������������������������������������������������low���high������
• findKth���������������������������������K������������������������������������������������K������������������k���������������������������������
• partition���������������������������������������������������������������������������������������������������

������

������������������������������������������������������������O(n)������������������������������������������������������������������������������������������������