# 215. Kth Largest Element in an Array (Medium)

## 1.問題

* 找出Array中第Kth大的元素

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LI-9mZpJXh4v5lHdy1J%2F-LI-AeXaixjxV1GWe2Y3%2F2018072201.jpg?alt=media\&token=185d750d-b95a-41eb-8c8d-95c620b9aecd)

## &#x20;2.想法&#x20;

* 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

![](https://901207480-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LGKoChvN9am4__HCIRK%2F-LI-9mZpJXh4v5lHdy1J%2F-LI-B_6ZLvGTffl6_ouV%2F2018072202.jpg?alt=media\&token=29c2debe-f1a5-400d-9c81-4c5606e654f2)
