leetcode 215. Kth Largest Element in an Array

小鱼儿 2023-07-05 05:25 77阅读 0赞

目录

一、问题分析

二、代码实现

1、排序

采用内置排序

采用冒泡排序

基数排序

2、堆

采用大顶堆

采用小顶堆

3、快速选择

递归版本

迭代版本

将输入数组随机化

采用中间下标的元素作为参照元素

采用BFPTR算法对参照元素的选取进行优化

https://leetcode.com/problems/kth-largest-element-in-an-array/

返回数组中第k大的元素

一、问题分析

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

输出的是第k大的元素，注意不是第k大的不同元素。另外，k总是大于等于1。

二、代码实现

1、排序

采用内置排序

采用Arrays.sort()，然后返回nums[nums.length-k]即可，时间为O(nlogn)。

  1. import java.util.Arrays;
  2. import java.util.Collections;
  3. class Solution {
  4.     public int findKthLargest1(int[] nums, int k) {
  6.         //排序
  7.         Arrays.sort(nums);
  8.         return nums[nums.length-k]; 
  10.         //Arrays.sort(nums, Collections.reverseOrder()); 
  11.         //return nums[k - 1];
  12.     }
  13. }

采用冒泡排序

采用用冒泡的方式，进行k轮冒泡。

  1. class Solution {
  3.     public int findKthLargest1(int[] nums, int k) {
  5.         //冒泡
  6.         for (int i=0; i<k; i++) {   //控制冒泡的轮数为k
  7.             for (int j=0; j<nums.length-1; j++) {
  8.                 if (nums[j] > nums[j+1]) {
  9.                     int temp = nums[j];
  10.                     nums[j] = nums[j+1];
  11.                     nums[j+1] = temp;
  12.                 }
  13.             }
  14.         }        
  15.         return nums[nums.length-k];
  16.     }
  17. }

基数排序

  1. class Solution {
  3.     //LSD radix sort
  4.     public int findKthLargest9(int[] nums, int k) {
  5.         final int R = (1 << 8);
  6.         final int bitmask = R - 1;
  7.         int[] aux = new int[nums.length];
  8.         for (int i = 0; i < 4; i++) {
  9.             int[] count = new int[R + 1];
  10.             for (int num : nums) {
  11.                 int c = (num >>> (i * 8)) & bitmask;
  12.                 count[c + 1]++;
  13.             }
  14.             for (int r = 0; r < R; r++) count[r + 1] += count[r];
  15.             if (i == 3) {
  16.                 int shift1 = count[R] - count[R/2];
  17.                 int shift2 = count[R/2];
  18.                 for (int r = 0; r < R/2; r++)
  19.                     count[r] += shift1;
  20.                 for (int r = R/2; r < R; r++)
  21.                     count[r] -= shift2;
  22.             }
  23.             for (int num : nums) {
  24.                 int c = (num >>> (i * 8)) & bitmask;
  25.                 aux[count[c]++] = num;
  26.             }
  27.             System.arraycopy(aux, 0, nums, 0, nums.length);
  28.         }
  29.         return nums[nums.length - k];
  30.     }
  32. }

2、堆

采用大顶堆

采用大顶堆装入所有元素，然后删除k-1个元素，剩下的堆顶元素即为所求，时间为O(n+klogn)。

  1. import java.util.PriorityQueue;
  2. import java.util.Collections;
  3. class Solution {
  5.     public int findKthLargest3(int[] nums, int k) {
  7.         //大顶堆
  8.         //PriorityQueue heap = new PriorityQueue(Collections.reverseOrder()); //error
  9.         PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder()); 
  10.         //
  11.         /*
  12.         Queue<Integer> PQ= new PriorityQueue<>(nums.length, new Comparator<Integer>() {
  13.             @Override
  14.             public int compare(Integer o1, Integer o2) {
  15.                 if(o1>o2) return -1;
  16.                 else if(o1<o2) return 1;
  17.                 else return 0;
  18.             }
  19.         } );
  20.         */
  21.         for (int i=0; i<nums.length; i++) {
  22.             heap.add(nums[i]);
  23.         }
  24.         for (int i=0; i<k-1; i++) {
  25.             heap.poll();
  26.         }
  28.         return heap.peek(); //error: incompatible types: Object cannot be converted to int
  29.     }
  31. }

采用小顶堆

采用小顶堆装入所有元素，同时控制元素个数在k个，当数组遍历完成之后，堆顶元素即为所求，时间为O(n*logk)。

  1. import java.util.PriorityQueue;
  2. import java.util.Collections;
  3. class Solution {
  5.     public int findKthLargest4(int[] nums, int k) {
  6.         //小顶堆
  7.         PriorityQueue<Integer> heap = new PriorityQueue<Integer>(k + 1);
  8.         /*
  9.         PriorityQueue<Integer> heap =
  10.             new PriorityQueue<Integer>((n1, n2) -> n1 - n2);
  11.         */
  13.         for(int e : nums) {
  14.             heap.add(e);
  16.             if (heap.size() > k) {
  17.                 heap.poll();
  18.             }
  19.         }
  21.         return heap.poll();
  22.     }
  24. }

3、快速选择

采用快排的划分方法，平均时间复杂度为O(n)，最坏时间复杂度为O(n^2)。

递归版本

主要思路是不断划分数组，如果参照元素后面的元素个数count（包括参照元素）等于k，直接返回参照元素；如果小于k，则令k = k - count，在左边继续找；如果大于k，则k不变，在右边继续找。

  1. class Solution {
  3.     public int findKthLargest5(int[] nums, int k) {
  4.         //快速选择
  5.         return quickSelect(nums, 0, nums.length-1, k);
  6.     }
  7.     private int quickSelect(int[] nums, int low, int high, int k) {
  8.         int pivot = low;
  10.         for (int i=low; i<high; i++) {
  11.             if (nums[i] <= nums[high]) {
  12.                 swap(nums, i, pivot++);
  13.             }
  14.         }
  15.         swap(nums, high, pivot);
  17.         int count = high - pivot + 1;    //大于等于nums[pivot]的元素个数
  18.         if (count == k) {
  19.             return nums[pivot];
  20.         }
  21.         if (count > k) {
  22.             return quickSelect(nums, pivot+1, high, k);    //返回右边部分
  23.         }
  24.         return quickSelect(nums, low, pivot-1, k-count);  
  25.     }
  26.     private void swap(int[] nums, int i, int j) {
  27.         int temp = nums[i];
  28.         nums[i] = nums[j];
  29.         nums[j] = temp;
  30.     }
  32. }

迭代版本

所求元素在数组排序后的下标为index = nums.length-k（找第k大的元素等价于找第n-k+1小的元素），因此主要思路是不断划分数组，直到找到一个下标等于index的参照元素，将其返回。

  1. class Solution { 
  3.      public int findKthLargest6(int[] nums, int k) {
  4.         k = nums.length - k;   //第k大的元素在排序后应该所在的位置
  6.         int l = 0, r = nums.length - 1;
  7.         while (l <= r) {
  8.             int i = l; // partition [l,r] by A[l]: [l,i]<A[l], [i+1,j)>=A[l]
  9.             for (int j = l + 1; j <= r; j++) {
  10.                 if (nums[j] < nums[l]) {
  11.                     swap(nums, j, ++i);
  12.                 }
  13.             }
  14.             swap(nums, l, i);   //i-1为最后一个小于参照元素的元素的下标，i为参照元素
  16.             if (k < i) r = i - 1;
  17.             else if (k > i) l = i + 1;
  18.             else return nums[i];    //找到一个下标等于所求下标的参照元素
  19.         }
  21.         return -1; //k非法的情况
  22.     }
  23.     private void swap(int[] nums, int i, int j) {
  24.         int temp = nums[i];
  25.         nums[i] = nums[j];
  26.         nums[j] = temp;
  27.     }
  29. }

将输入数组随机化

由于输入数组可能基本有序以及选取参照元素方式的单一，导致时间可能为O(n^2）。这里先对输入数组打乱所有元素的顺序，当然，也可以在选取参照元素的时候，采用随机元素或者下标为中间的元素。

  1. class Solution {
  3.     public int findKthLargest(int[] nums, int k) {
  4.         shuffle(nums);
  5.         return findK(nums, nums.length - k, 0, nums.length - 1);
  6.     }
  7.     private int findK(int[] nums, int k, int l, int r) {
  8.         int pivotIndex = partition(nums, l, r);
  10.         if (k < pivotIndex)
  11.             return findK(nums, k, l, pivotIndex - 1);
  12.         else if (k > pivotIndex)
  13.             return findK(nums, k, pivotIndex + 1, r);
  14.         else // k == pivotIndex
  15.             return nums[k];
  16.     }
  17.     private int partition(int[] a, int lo, int hi) {
  18.         int pivotIdx = lo; // bad practice
  19.         int pivotVal = a[pivotIdx];
  21.         // put pivot last
  22.         swap(a, pivotIdx, hi);
  23.         int storeIdx = lo;
  25.         for (int i = lo; i < hi; i++) {
  26.             if (a[i] <= pivotVal) {
  27.                 swap(a, i, storeIdx);
  28.                 storeIdx++;
  29.             }
  30.         }
  31.         swap(a, storeIdx, hi);  //storeIdx+1是第一个大于参照元素的元素，storeIdx为参照元素
  32.         return storeIdx;
  33.     }
  34.     private void shuffle(int[] a) {
  35.         for (int i = a.length - 1; i >= 0; i--) {
  36.             int j = (int) (Math.random() * (i + 1)); // j=0..i
  37.             swap(a, i, j);
  38.         }
  39.     }
  40.     private void shuffle2(int[] a) {
  41.         final Random random = new Random();
  43.         for(int ind = 1; ind < a.length; ind++) {
  44.             final int r = random.nextInt(ind + 1);
  45.             exch(a, ind, r);
  46.         }
  47.     }
  48.     private void swap(int[] nums, int i, int j) {
  49.         int temp = nums[i];
  50.         nums[i] = nums[j];
  51.         nums[j] = temp;
  52.     }
  54. }

采用中间下标的元素作为参照元素

在区间[left, right]中选取参照元素时，选取的参照元素nums[mid]满足nums[left] <= nums[mid] <= nums[right]，可以有效避免最坏情况的出现（参照元素总是选中区间最大值或最小值）。此种方式比前面几种快得多，运行时间可以超过98%的Java提交。

  1. class Solution {
  3.     public int findKthLargest8(int[] nums, int k) {
  4.         return select(nums, k-1);
  5.     }
  6.     // Quick select
  7.     private int select(int[] nums, int k) {
  8.         int left = 0, right = nums.length-1;
  9.         while(true) {
  10.             if(left == right)
  11.                 return nums[left];
  12.             int pivotIndex = medianOf3(nums, left, right);
  13.             pivotIndex = partition(nums, left, right, pivotIndex);
  14.             if(pivotIndex == k)
  15.                 return nums[k];
  16.             else if(pivotIndex > k)
  17.                 right = pivotIndex-1;
  18.             else
  19.                 left = pivotIndex+1;
  20.         }
  21.     }
  22.     //Use median-of-three strategy to choose pivot，很强大的选取参照元素操作的优化方式
  23.     private int medianOf3(int[] nums, int left, int right) {    
  24.         //让nums[right]<=nums[mid]<=nums[left] 
  25.         int mid = left + (right - left) / 2;
  26.         if(nums[right] > nums[left])
  27.             swap(nums, left, right);
  28.         if(nums[right] > nums[mid])
  29.             swap(nums, right, mid);
  30.         if(nums[mid] > nums[left])
  31.             swap(nums,left, mid);
  33.         //返回mid
  34.         return mid;
  35.     }
  36.     private int partition(int[] nums, int left, int right, int pivotIndex) {
  37.         int pivotValue = nums[pivotIndex];
  38.         swap(nums, pivotIndex, right);
  40.         int index = left;
  41.         for(int i = left; i < right; ++i) {
  42.             if(nums[i] > pivotValue) {
  43.                 swap(nums, index, i);
  44.                 ++index;
  45.             }
  46.         }
  47.         swap(nums, right, index);
  49.         return index;
  50.     }
  52. }

采用BFPTR算法对参照元素的选取进行优化

通过选取中位数的中位数作为参照元素，来避免单一地选取最低/最高下标的元素所导致的最坏情况（O(n^2)）的发生。具体来说，把元素分为元素个数为5的小组（最后一组元素个数可能为n mod 5），分别进行插入排序。将各个小组的中位数移到数组前面，然后重复以上操作，直到只剩一个元素，将其作为参照元素。

  1. class Solution {
  3.     public int findKthLargest(int[] nums, int k) {
  4.         return bfprt(nums, 0, nums.length-1, k);
  5.     }
  6.     private int bfprt(int[] a, int l, int r, int k) {
  7.         int p = findMid(a, l, r);   //寻找中位数的中位数
  8.         int i = partition111(a, l, r, p);
  10.         //int m = i - l + 1;
  11.         int m = r - i + 1;
  12.         if (m == k) {
  13.             return a[i];
  14.         }
  15.         if (m > k) {
  16.             //return bfprt(a, l, i-1, k);
  17.             return bfprt(a, i+1, r, k);
  18.         }
  19.         //return bfprt(a, i+1, r, k-m);
  20.         return bfprt(a, l, i-1, k-m);
  21.     }
  22.     private int findMid(int[] a, int l, int r) {
  23.         if (l == r) {
  24.             return l;
  25.         }
  27.         //处理前几组元素
  28.         int i = 0, n = 0;
  29.         for (i=l; i<r-5; i+=5) {
  30.             insertionSort(a, i, i+4);
  31.             n = i - l;
  32.             swap(a, l+n/5, i+2);
  33.         }
  34.         //处理最后一组元素（剩余元素）
  35.         int num = r - i + 1;
  36.         if (num > 0) {
  37.             insertionSort(a, i, i+num-1);
  38.             n = i - l;
  39.             swap(a, l+n/5, i+num/2);
  40.         }
  42.         n /= 5;
  43.         if (n == 0) {
  44.             return l;
  45.         }
  46.         return findMid(a, l, l + n);
  48.     }
  49.     private void insertionSort(int[] a, int l, int r) {
  50.         for (int i=l+1; i<=r; i++) {
  51.             if (a[i-1] > a[i]) {
  52.                 int temp = a[i];
  53.                 int j = i;
  54.                 while (i>i && a[j-1]>temp) {
  55.                     a[j] = a[j-1];
  56.                     j--;
  57.                 }
  58.                 a[j] = temp;
  59.             }
  60.         }
  61.     }
  62.     private int partition(int[] a, int l, int r, int p) {
  63.         swap(a, l, p);
  64.         int pivot = a[l];
  66.         int i = l, j = r;
  67.         while (i < j) {
  68.             while (a[j]>pivot && i<j) {
  69.                 j--;
  70.             }
  71.             a[i] = a[j];
  72.             while (a[i]<=pivot && i<j) {
  73.                 i++;
  74.             }
  75.             a[j] = a[i];
  76.         }
  77.         a[i] = pivot;
  78.         return i;
  79.     }
  81. }

参考：

https://zhuanlan.zhihu.com/p/31498036

https://blog.csdn.net/laojiu_/article/details/54986553

https://www.jianshu.com/p/495e5019669c

发表评论

表情：
评论列表 （有 0 条评论，77人围观）

还没有评论，来说两句吧...

相关阅读