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

        #若滿足，表示大於k的太多了 
        #將範圍縮小遞迴求解:
        if k<=len(big):
            return self.findKthLargest(big,k)

* Step4:
* 否則表示K數量太多
* K多過於 **len(big)+pivot的數量**
* 所以遞迴從small中找(k-len(big)-pivot的數量)

        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:

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++:

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