# 1985. Find the Kth Largest Integer in the Array
###### tags: `Leetcode` `Medium` `QuickSort` `FaceBook` `Priority Queue`
Link: https://leetcode.com/problems/find-the-kth-largest-integer-in-the-array/
## 思路
和其他用quicksort或者priority queue找第k大的值很像，但时间复杂度有差别，建议直接把quicksort的代码背下来，不然总是写错555
### 思路一 Priority Queue O(NlogK * M) O(K)
Time: O(NlogK * M), where N <= 10^4 is length of nums array, K <= N is the kth largest element need to output, M <= 100 is length of each num.

Explain: The MinHeap keeps up to K elements, **each heappush/heappop operator costs O(logK)**. We iterate all elements in nums and push/pop to the MinHeap N times. **We need to multiply by M as well, since in the worst case, we need to compare strings by their lexicographically.**

Space: O(K)

### 思路二 QuickSort average O(N * M) O(1)
但是不知道为啥在leetcode跑的时候花了超级长时间

## Code
### 思路一 Priority Queue

class Solution {
    public String kthLargestNumber(String[] nums, int k) {
        Queue<String> pq = new PriorityQueue<>(new Comparator<>(){
           public int compare(String a, String b){
               if(a.length()!=b.length()){
                   return a.length()-b.length();
               }
               else{
                   return a.compareTo(b);
               }
           } 
        });
        for(String num:nums){
            pq.add(num);
            if(pq.size() > k){
                pq.poll();
            }
        }
        return pq.peek();
    }
}

### 思路二

class Solution {
    Random rand;
    
    public int compare(String a, String b){
       if(a.length()!=b.length()){
           return b.length()-a.length();
       }
       else{
           return b.compareTo(a);
       }
    }
    
    public String kthLargestNumber(String[] nums, int k) {
        rand = new Random();
        quickSort(nums, k, 0, nums.length);
        return nums[k-1];
    }
    
    public void quickSort(String[] nums, int k, int start, int end){
        int selected = start + rand.nextInt(end-start);
        swap(nums, selected, start);
        int idx = start;
        for(int i = start+1;i < end;i++){
            if(compare(nums[start], nums[i])>0){
                swap(nums, ++idx, i);
            }
        }
        swap(nums, idx, start);
        if(k == idx-start+1){
            return;
        }
        else if(k < idx-start+1){
            quickSort(nums, k, start, idx);
        }
        else{
            quickSort(nums, k-(idx-start+1), idx+1, end);
        }
    }
    
    public void swap(String[] nums, int a, int b){
        String temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}