LeetCode: 215. Kth Largest Element in an Array 数组中第k大元素

梦里梦外; 2021-06-24 16:10 281阅读 0赞

**试题：**  
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.  
**代码：**  
topk或者kth element问题通常可以使用快排和堆排解决。快排找出kth后再遍历一遍就能找到topk；堆排的堆顶就是kth element。

class Solution {
        public int findKthLargest(int[] nums, int k) {
            Arrays.sort(nums);
            return nums[nums.length-k];
        }
    }

class Solution {
        public int findKthLargest(int[] nums, int k) {
            PriorityQueue<Integer> que = new PriorityQueue<Integer>(k);
            for(int num : nums){
                if(que.size()<k)
                    que.offer(num);
                else if(que.peek()<num){
                    que.offer(num);
                    que.poll();
                }
            }
            return que.peek();
        }
    }

//快速选择法
    class Solution {
        public int findKthLargest(int[] nums, int k) {
            k = nums.length-k;
            int low=0, high=nums.length-1;
            while(low<high){      //不需要等于，当low=high-1时，已经排序好数组了。
                int part = partition(nums, low, high);
                if(part==k){
                    break;
                }else if(part<k){
                    low = part+1;
                }else{
                    high = part-1;
                }
                
            }
            return nums[k];
        }
        
        private int partition(int[] nums, int low, int high){
            int left=low, right=high+1;
            while(true){
                while(nums[++left]<nums[low] && left<high);
                while(nums[--right]>nums[low] && right>low);
                if(left>=right) break;
                swap(nums,left,right);            
            }
            swap(nums,low,right);
            return right;
        }
        
        private void swap(int[] nums, int left, int right){
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }

class Solution {
        public int findKthLargest(int[] nums, int k) {
            int len = nums.length;
            k = len - k;
            quickSort(nums, 0, len-1, k);
            return nums[k];
        }
        
        public void quickSort(int[] nums, int start, int end, int target){
            if(start < end){
                int mid = partion(nums, start, end);
                if(mid == target){
                    return;
                }else if(mid > target){
                    quickSort(nums, start, mid-1, target);
                }else if(mid < target){
                    quickSort(nums, mid+1, end, target);
                }
            }
        }
        
        public int partion(int[] nums, int start, int end){
            int pivot = nums[start];
            int left = start, right = end;
            while(left < right){
                while(left < right && nums[right] >= pivot) right--;
                while(left < right && nums[left] <= pivot) left++;
                if(left < right){
                    swap(nums, left, right);
                }
            }
            swap(nums, start, right);
            return right;
        }
        
        public void swap(int[] nums, int i, int j){
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
            return;
        }
    }