215. Kth Largest Element in an Array (Medium)

1.問題

• 找出Array中第Kth大的元素

2.想法

• Quick sort

3.程式碼

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(nums.empty()) {
            return 0;
        }
        quickSort(nums, k, 0, nums.size() - 1);
        return nums[k - 1];
    }
private:
    int partition(vector<int>& listToSort, int low, int high) {
        int pivort = listToSort[high], l = low, h = high;
        while (l < h) {
            while (listToSort[l] > pivort) {
                l++;
            }
            
            while (listToSort[h] <= pivort) {
                h--;
            }
            
            if (l < h) {
                swap(listToSort, l, h);
            }
        }
        swap(listToSort, l, high);
        return l;
    }
    
    void quickSort(vector<int>& listToSort, int k, int low, int high) {
        if (low >= high) {
            return;
        }
        int pivotIndex = partition(listToSort, low, high);
        if (pivotIndex + 1 < k) {
            quickSort(listToSort, k, pivotIndex + 1, high);
        } else {
            quickSort(listToSort, k, low, pivotIndex - 1);
        }
    }
    
    void swap(vector<int>& list, int num1, int num2) {
        int tmp = list[num1];
        list[num1] = list[num2];
        list[num2] = tmp;
    }
};

4.Performance