---
# System prepended metadata

title: 215. Kth Largest Element in an Array
tags: [Leetcode, medium, python, quickselect, c++, Top 100 Liked Questions, sort]

---

###### tags: `Leetcode` `medium` `sort` `quickselect` `python` `c++` `Top 100 Liked Questions`

# 215. Kth Largest Element in an Array

## [題目連結:] https://leetcode.com/problems/kth-largest-element-in-an-array/description/

## 題目:
Given an integer array ```nums``` and an integer ```k```, return the ```kth``` largest element in the array.

Note that it is the ```kth``` largest element in the sorted order, not the ```kth``` distinct element.

You must solve it in ```O(n)``` time complexity.

**Example 1:**
```
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
```
**Example 2:**
```
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
```

## 解題想法:
* 題目為要求O(n)時間求出第K大的數字，於未排序且可能有重複數字的數組

* 使用Qick Select
    * Step1:
        * pivot=random.choice(nums) #隨機選一點
        * small=[ ] #存小於pivot的數
        * big=[ ] #存大於pivot的數
    * Step2:
        * 遍歷所有數字存於small與big中
    * Step3:
        * 先看len(big)數量是否大於滿足k
        ``` python=
        #若滿足，表示大於k的太多了 
        #將範圍縮小遞迴求解:
        if k<=len(big):
            return self.findKthLargest(big,k)
        ```
    * Step4:
        * 否則表示K數量太多
        * K多過於 **len(big)+pivot的數量**
        * 所以遞迴從small中找(k-len(big)-pivot的數量)
        ``` python=
        elif k> (len(nums)-len(small)):
            return self.findKthLargest(small,k-(len(nums)-len(small)))
        ```
        * **len(big)+pivot的數量** 
        * 即為: **len(num)-len(small)**
            * 因為對於small、big存入的數字，皆不考慮等於pivot的值，所以若pivot有重複:
                * 有可能 len(nums)>= len(big)+len(small) 


## Python:
``` python=
import random
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        #Quick select
        pivot = random.choice(nums)
        small=[]
        big = []
        #先分堆O(n)
        for i in nums:
            #不用等於 因為不考慮重複值 所以有可能 len(nums)>= len(big)+len(small) 
            if i<pivot:
                small.append(i)
            elif i>pivot:
                big.append(i)
        #看big數量是否滿足k
        if k<=len(big):
            return self.findKthLargest(big,k)
        #要用len(num)-len(small)
        #否則為K的數量還是太多了 K多過於 len(big)+pivot的數量
        # len(big)+pivot的數量 即為: len(num)-len(small)
        elif k> (len(nums)-len(small)):
            return self.findKthLargest(small,k-(len(nums)-len(small)))
        return pivot
                
result = Solution()
nums = [3,2,3,1,2,4,5,5,6]
k = 4
ans = result.findKthLargest(nums,k)
print(ans)
```

## C++:
``` cpp=
#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int random = rand()% nums.size();
        int pivot = nums[random];
        vector<int> small, big;
        //collect
        for (int val: nums){
            if (val<pivot)
                small.push_back(val);
            else if (val>pivot)
                big.push_back(val);
        }
        //compare
        if (k<=big.size())
            return findKthLargest(big, k);
        else if (k> nums.size()-small.size())
            return findKthLargest(small, k-(nums.size()-small.size()));
        else
            return pivot;
    }
};

int main(){
    Solution* res= new Solution();
    vector<int> nums={3,2,1,5,6,4};
    int k=2;
    int ans=res->findKthLargest(nums,k);
    cout<<ans<<endl;
    return 0;
}
```