【LeetCode刷題筆記】215.數組中的第k個最大元素

• 題目：在未排序的數組中找到第 k 個最大的元素。請注意，你需要找的是數組排序後的第 k 個最大的元素，而不是第 k 個不同的元素。

示例：輸入: [3,2,1,5,6,4] 和 k = 2

輸出: 5

• 分治，利用快速排序的思想

  根據快速排序的思想，确定一個數讓其做分割點，左邊的數字都比它小或相等，右邊的數都比其大。每次分割結束後比較從分割點到最右端的距離，如果相等，就說明分割點右邊有k - 1個數字比它更大，那麼它就是第k大的數字，如果小于，說明右邊比分割點大的數字不足k個，那麼第k大的點應該在左邊，反之同理。

public int findKthLargest(int[] nums, int k){
        return partition(nums, k, 0, nums.length - 1);
    }

    private int partition(int[] nums, int k, int left, int right){
        int low = left;
        int high = right;
        int pivot = nums[low];

        while (low < high){
            while (low < high){
                if (pivot <= nums[high])
                    high--;
                else {
                    nums[low] = nums[high];
                    break;
                }
            }
            while (low < high){
                if (pivot >= nums[low])
                    low++;
                else {
                    nums[high] = nums[low];
                    break;
                }
            }
        }
        int parIndex = low;
        nums[low] = pivot;
        if (right - low + 1 == k)
            return nums[low];
        else if (right - low + 1 < k)
        // 注意這裡，k要減去相應的距離，因為右面已經有right - low + 1個數字比第k個數字大了，是以在左邊隻要找
        // 第k - (right - low + 1)個大的數字
            return partition(nums, k - (right - low + 1), left, parIndex - 1);
        else
            return partition(nums, k, parIndex + 1, right);
    }