排序LeetCode 215 Kth Largest Element in an Array

LeetCode 215

Kth Largest Element in an Array

• Problem Description：

  傳回數組的第k大元素，可采用快速排序的方法。快速排序每周遊一次就确定一個元素在數組中的最終位置，比該元素大的位于該元素右側，比該元素小的位于該元素左側。通過每次周遊後比較确定的位置和k 值大小，縮小區間範圍，最終即可求出第k大元素。

  具體的題目資訊：

  https://leetcode.com/problems/kth-largest-element-in-an-array/description/

• Example:

  

• Solution:

class Solution {
public:
    int Partition(vector<int>& nums, int low, int high) {
        int pivot = nums[low];
        while(low<high) {
            while(low<high && nums[high]>= pivot) high--;
            nums[low] = nums[high];
            while(low<high && nums[low]<= pivot) low++;
            nums[high] = nums[low];
        }
        nums[low] = pivot;
        return low;
    }
    int findKthLargest(vector<int>& nums, int k) {
        if (nums.size() == ) return ;
        if (nums.size() == ) return nums[];
        k = nums.size()-k;
        int low = , high = nums.size()-;
        while(low<high) {
            int pivot = Partition(nums, low, high);
            if (pivot == k) {
                break;
            } else if (pivot<k) {
                low = pivot+;
            } else {
                high = pivot-;
            }
        }
        return nums[k];
    }
};