Kth Largest Element in an Array

Find the kth 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.

可以用priorityqueue，但是不是考察点

priority queue offer and add :O(logN); poll remobe o(1), contains o(N)

Time o(nlogk),space o(k)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0)
            return 0;
        
        
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) ->a - b);
        
        for(int i = 0; i < nums.length;i++){
            if(queue.size() < k){
                queue.offer(nums[i]);
            }
            
            else{
                if(nums[i] > queue.peek()){
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }
        }
        
        return queue.peek();
    }
}

这题的考察点是quick sort

Kth Largest Element in an Array - LeetCodeLeetCode

时间复杂度 o(n),

This is only the partition part of quick sort, which places your pivot element at the correct position, such that all the elements before it are less than the pivot value, and all elements after are greater. You don't care if the rest of the array is sorted or not.

After each partition, you would get a shorter array to partition. the length decrease exponentially (one half each time in average), you sum up 1 + 1/2 + 1/4 + .. = 2. Therefore, the complexity is O(2N) ~ O(N)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0 || nums.length < k || k < 0){
            return -1;
        }
        
        shuffle(nums);
        
        
        int targetIndex = nums.length - k;
        
        int low = 0, hight = nums.length - 1;
        
        while(true){
            int j = partation(nums,low, hight);
            
            if(targetIndex > j){
                low = j+1;
            }
            
            else if(targetIndex < j){
                hight--;
            }else{
                break;
            }
        }
        
        return nums[targetIndex];
        
    }
    
    public int partation(int[] nums, int low, int hi){
        int pivotValue = nums[low];
        int pivotIndex = low;
        low++;
        //因为最后是和hi swap，所以hi的地方可以是pivotvalue
        while(low <= hi){
            if(nums[low] < pivotValue){
                low++;
            }
            
            else if(nums[hi] >= pivotValue){
                hi--;
            }else{
                swap(nums,low, hi);
            }
        }
        
        
        swap(nums,pivotIndex,hi);
        return hi;
    }
    
    public void swap(int[] nums,int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    
    public void shuffle(int[] nums){
        Random r = new Random();
        int rang = nums.length;
        for(int i = 0; i < nums.length ;i++){
            int next = r.nextInt(rang);
            swap(nums,i,next);
        }
    }
    
    
}