java---数组中第K个最大数

1:思路分析

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入:
[3,2,1,5,6,4] 和
k = 2
输出: 5
示例 2:
输入:
[3,2,3,1,2,4,5,5,6] 和
k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

2:具体实现

对数组进行快速排序

 private static int partation(int[] number, int left, int right) {
        if (number == null || number.length <= 0) {
            return 0;
        }
        int mid = number[left];------------------//基准数
        while (left < right) {
            while (left < right && number[right] > mid) {//从右边开始将小于基准数的放在左边
                right--;
            }
            number[left] = number[right];
            while (left < right && number[left] < mid) {//从左边开始将大于基准数的放在右边
                left++;
            }
            number[right] = number[left];
        }
        number[left] = mid;-----------------//排序完成之后中间的那个元素
        return left;
    }

上面完成之后数组就是一个有序数组了

private static int findKthLargest(int[] number, int k) {
        if (number == null || number.length <= 0 || k > number.length) {
            return 0;
        }
        int left =0;
        int right = number.length -1;
        while (left < right) {
            int pos = partation(number, left, right);-----//有序数组中间元素的index
            if (pos == k -1) {--------------//找到直接跳出循环
                break;
            } else if (pos < k -1) {--------------//如果小于k-1，那么向数组右边继续查找
                left = pos + 1;
            } else {-//如果大于k-1，那么向数组左边继续查找
                right = pos -1;
            }
        }
        return number[k-1];
    }