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

Find the **k**th largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

**Example 1:**

```
Input: [3,2,1,5,6,4] and k = 2
Output: 5
```

**Example 2:**

```
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
```

**Note:**\
You may assume k is always valid, 1 ≤ k ≤ array's length.

**Solution**

QuickSelect

根據lastPrivotIndex，決定要往哪邊進行sort，若lastPrivotIndex > k，代表 k在 lastPrivotIndex左邊，所以sort左半，反之sort 右半

**TimeComplexity: O(n)**&#x20;

Discard half each time: n+(n/2)+(n/4)..1 = n + (n-1) = O(2n-1) = O(n), because n/2+n/4+n/8+..1=n-1.

```
    public int findKthLargest(int[] nums, int k) {
        shuffle(nums);
        return quickSelect(nums, 0, nums.length-1,  k-1);
    }
    
    public void shuffle(int[] nums){
        for(int i = 0 ; i < nums.length; i++){
            swap(nums, i, (int)(Math.random()*(nums.length-1)));
        }
    }
    
    public int quickSelect(int[] nums, int start, int end, int k){
        int lastPrivotIndex = start;
        int pivot = nums[end];
        for(int i = start; i < end; i++){
            if(pivot < nums[i]){
                swap(nums, lastPrivotIndex, i);
                lastPrivotIndex++;
            }
        }
        swap(nums, lastPrivotIndex, end);
        if(lastPrivotIndex== k){
            return pivot;
        }
        else if (lastPrivotIndex< k){
            //k is on the right ride
            return quickSelect(nums, lastPrivotIndex+1, end, k);
        }
        else {
            //k is on the left ride
            return quickSelect(nums, start, lastPrivotIndex-1, k);
        }
    }
    
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
```
