215. 数组中的第K个最大元素 BFPRT最牛解法

举报
兔老大 发表于 2021/04/24 01:31:51 2021/04/24
【摘要】 在未排序的数组中找到第 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 说明: 你可以假设 k 总是有效的,且 1 ≤ 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
说明:

你可以假设 k 总是有效的,且 1 ≤ k ≤ 数组的长度。

思路:堆、改进快排、BFPRT

解释链接


  
  1. public class Solution {
  2. /*
  3. //前k小
  4. public static int[] getMinKNumsByBFPRT(int[] arr, int k) {
  5. if (k < 1 || k > arr.length) {
  6. return arr;
  7. }
  8. int minKth = findKthLargest(arr, k);
  9. int[] res = new int[k];
  10. int index = 0;
  11. for (int i = 0; i != arr.length; i++) {
  12. if (arr[i] < minKth) {
  13. res[index++] = arr[i];
  14. }
  15. }
  16. for (; index != res.length; index++) {
  17. res[index] = minKth;
  18. }
  19. return res;
  20. }
  21. */
  22. //第k小
  23. public static int findKthLargest(int[] arr, int K) {
  24. int[] copyArr = copyArray(arr);
  25. return select(copyArr, 0, copyArr.length - 1, arr.length-K);
  26. }
  27. public static int[] copyArray(int[] arr) {
  28. int[] res = new int[arr.length];
  29. for (int i = 0; i != res.length; i++) {
  30. res[i] = arr[i];
  31. }
  32. return res;
  33. }
  34. //给定一个数组和范围,求第i小的数
  35. public static int select(int[] arr, int begin, int end, int i) {
  36. if (begin == end) {
  37. return arr[begin];
  38. }
  39. int pivot = medianOfMedians(arr, begin, end);//划分值
  40. int[] pivotRange = partition(arr, begin, end, pivot);
  41. if (i >= pivotRange[0] && i <= pivotRange[1]) {
  42. return arr[i];
  43. } else if (i < pivotRange[0]) {
  44. return select(arr, begin, pivotRange[0] - 1, i);
  45. } else {
  46. return select(arr, pivotRange[1] + 1, end, i);
  47. }
  48. }
  49. //在begin end范围内进行操作
  50. public static int medianOfMedians(int[] arr, int begin, int end) {
  51. int num = end - begin + 1;
  52. int offset = num % 5 == 0 ? 0 : 1;//最后一组的情况
  53. int[] mArr = new int[num / 5 + offset];//中位数组成的数组
  54. for (int i = 0; i < mArr.length; i++) {
  55. int beginI = begin + i * 5;
  56. int endI = beginI + 4;
  57. mArr[i] = getMedian(arr, beginI, Math.min(end, endI));
  58. }
  59. return select(mArr, 0, mArr.length - 1, mArr.length / 2);
  60. //只不过i等于长度一半,用来求中位数
  61. }
  62. //经典partition过程
  63. public static int[] partition(int[] arr, int begin, int end, int pivotValue) {
  64. int small = begin - 1;
  65. int cur = begin;
  66. int big = end + 1;
  67. while (cur != big) {
  68. if (arr[cur] < pivotValue) {
  69. swap(arr, ++small, cur++);
  70. } else if (arr[cur] > pivotValue) {
  71. swap(arr, cur, --big);
  72. } else {
  73. cur++;
  74. }
  75. }
  76. int[] range = new int[2];
  77. range[0] = small + 1;
  78. range[1] = big - 1;
  79. return range;
  80. }
  81. //五个数排序,返回中位数
  82. public static int getMedian(int[] arr, int begin, int end) {
  83. insertionSort(arr, begin, end);
  84. int sum = end + begin;
  85. int mid = (sum / 2) + (sum % 2);
  86. return arr[mid];
  87. }
  88. //手写排序
  89. public static void insertionSort(int[] arr, int begin, int end) {
  90. for (int i = begin + 1; i != end + 1; i++) {
  91. for (int j = i; j != begin; j--) {
  92. if (arr[j - 1] > arr[j]) {
  93. swap(arr, j - 1, j);
  94. } else {
  95. break;
  96. }
  97. }
  98. }
  99. }
  100. //交换值
  101. public static void swap(int[] arr, int index1, int index2) {
  102. int tmp = arr[index1];
  103. arr[index1] = arr[index2];
  104. arr[index2] = tmp;
  105. }
  106. /*
  107. //打印
  108. public static void printArray(int[] arr) {
  109. for (int i = 0; i != arr.length; i++) {
  110. System.out.print(arr[i] + " ");
  111. }
  112. System.out.println();
  113. }
  114. */
  115. }

 

文章来源: fantianzuo.blog.csdn.net,作者:兔老大RabbitMQ,版权归原作者所有,如需转载,请联系作者。

原文链接:fantianzuo.blog.csdn.net/article/details/104079514

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。