> For the complete documentation index, see [llms.txt](https://jenhsuan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jenhsuan.gitbook.io/algorithm/leetcode/215.-kth-largest-element-in-an-array-medium.md).

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

## 1.問題

* 找出Array中第Kth大的元素

![](/files/-LI-AeXaixjxV1GWe2Y3)

##  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

![](/files/-LI-B_6ZLvGTffl6_ouV)