1:思路分析

在未排序的數(shù)組中找到第 k 個最大的元素。請注意，你需要找的是數(shù)組排序后的第 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 ≤ 數(shù)組的長度。

2:具體實現(xiàn)

對數(shù)組進行快速排序

 private static int partation(int[] number, int left, int right) {
        if (number == null || number.length <= 0) {
            return 0;
        }
        int mid = number[left];------------------//基準數(shù)
        while (left < right) {
            while (left < right && number[right] > mid) {//從右邊開始將小于基準數(shù)的放在左邊
                right--;
            }
            number[left] = number[right];
            while (left < right && number[left] < mid) {//從左邊開始將大于基準數(shù)的放在右邊
                left++;
            }
            number[right] = number[left];
        }
        number[left] = mid;-----------------//排序完成之后中間的那個元素
        return left;
    }

上面完成之后數(shù)組就是一個有序數(shù)組了

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);-----//有序數(shù)組中間元素的index
            if (pos == k -1) {--------------//找到直接跳出循環(huán)
                break;
            } else if (pos < k -1) {--------------//如果小于k-1，那么向數(shù)組右邊繼續(xù)查找
                left = pos + 1;
            } else {-//如果大于k-1，那么向數(shù)組左邊繼續(xù)查找
                right = pos -1;
            }
        }
        return number[k-1];
    }