题目链接

LeetCode

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

提示：

  • 1 <= k <= nums.length <= 104
  • -104 <= nums[i] <= 104

    解题思路

    方法一：优先队列

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
  4.         for(int num : nums){
  5.             if(pq.size() < k){
  6.                 pq.offer(num);
  7.             }else{
  8.                 if(pq.peek() < num){
  9.                     pq.poll();
  10.                     pq.offer(num);
  11.                 }
  12.             }
  13.         }
  14.         return pq.peek();
  15.     }
  16. }
  • 时间复杂度 O(n log n)
  • 空间复杂度 O(log n)


方法二：快速排序

利用快排思想直接缩小每次的范围。

  1. class Solution {
  2.     int index;
  3.     Random random;
  4.     public int findKthLargest(int[] nums, int k) {
  5.         random = new Random();
  6.         qSort(nums, 0, nums.length - 1, k);
  7.         return index;
  8.     }
  9.     private void qSort(int[] nums, int left, int right, int k){
  10.         if(left > right){
  11.             return;
  12.         }
  13.         swap(nums, left, left + random.nextInt(right - left + 1));
  14.         int val = nums[left];
  15.         int l = left, r = right;
  16.         while(l < r){
  17.             while(l < r && nums[r] >= val){
  18.                 --r;
  19.             }
  20.             if(l < r){
  21.                 nums[l++] = nums[r];
  22.             }
  23.             while(l < r && nums[l] < val){
  24.                 ++l;
  25.             }
  26.             if(l < r){
  27.                 nums[r--] = nums[l];
  28.             }
  29.         }
  30.         nums[l] = val;
  31.         // 大于等于val的正好有K个
  32.         if(right - l + 1 == k){
  33.             index = val;
  34.             return;
  35.         }
  36.         // 大于等于val的多余K个，继续在右半个区域查找第K大的值
  37.         if(right - l + 1 > k){
  38.             qSort(nums, l + 1, right, k);
  39.         }else{
  40.         // 大于等于val的小余K个，继续在左半个区域查找第K - (右边元素个数)大的值
  41.             qSort(nums, left, l - 1, k - right + l - 1);
  42.         }
  43.     }
  44.     private void swap(int[] nums,int i, int j){
  45.         int tmp = nums[i];
  46.         nums[i] = nums[j];
  47.         nums[j] = tmp;
  48.     }
  49. }
  • 时间复杂度 O(n)
  • 空间复杂度 O(log n)

    方法三：自己实现堆排序

  1. class Solution {
  2.     public int findKthLargest(int[] nums, int k) {
  3.         heapSort(nums);
  4.         return nums[nums.length - k];
  5.     } 
  6.     private void heapSort(int[] nums){
  7.         for(int i = nums.length / 2; i >= 0; --i){
  8.             buildMaxHeap(nums, nums.length, i);
  9.         }
  10.         for(int i = nums.length - 1; i > 0; --i){
  11.             swap(nums, 0, i);
  12.             buildMaxHeap(nums, i, 0);
  13.         }
  14.     }
  15.     private void buildMaxHeap(int[] nums, int len, int i){
  16.         int longest = i;
  17.         int left = 2 * i + 1;
  18.         int right = 2 * i + 2;
  19.         if(left < len && nums[left] > nums[longest]){
  20.             longest = left;
  21.         }
  22.         if(right < len && nums[right] > nums[longest]){
  23.             longest = right;
  24.         }
  25.         if(longest != i){
  26.             swap(nums, i, longest);
  27.             buildMaxHeap(nums, len, longest);
  28.         }
  29.     }  
  31.     private void swap(int[] nums, int left, int right){
  32.         int tmp = nums[left];
  33.         nums[left] = nums[right];
  34.         nums[right] = tmp;
  35.     }
  36. }
  • 时间复杂度 O(n)
  • 空间复杂度 O(log n)