LeetCode 腾讯精选50题--数组中的第K个最大元素

拼搏现实的明天。 2023-06-05 05:53 17阅读 0赞

好吧,不得不承认,书上看到的始终不是自己的,只有亲身时间过才会明白该怎么操作。

找数组中第K个最大元素,简而言之就是先排序,不论使用哪种算法,都需要先排序,确认位置,由于数组可以通过下标直接访问,所以我打算将数组按逆序排序,选择算法方面,一开始打算使用大顶堆的堆排序,可是想了下,快排的性能会更好一点,所以就采用快排了

具体思路如下:

  由于一开始为了让空间复杂度为O(1),所以踩了不少坑,最坑的就是找到中间位置,又要让比中间元素小的放在左边,又不打算移动中间位置,直接就崩了。。。惨惨惨。

  言归正传:

  1. 首先明确一点就是快排使用递归操作

  2. 其次利用三元法确定pivot,即元素的界,值小于pivot放在右侧,大于pivot的但在左侧

  3. 根据k的大小确定递归哪一侧

具体程序如下:

  1. 1 package algorithm;
  2. 2
  3. 3 public class QuickSort {
  4. 4
  5. 5 public int findKthLargest(int[] nums, int k){
  6. 6 if(nums.length < k){
  7. 7 return 0;
  8. 8 }
  9. 9 quickSort(nums,0,nums.length-1,k);
  10. 10
  11. 11 return nums[k-1];
  12. 12 }
  13. 13
  14. 14 private void quickSort(int[] nums,int left,int right,int k){
  15. 15
  16. 16 int center = (left+right)/2;
  17. 17 if(left >= right){
  18. 18 return;
  19. 19 }
  20. 20 int pivot = chosePivot(nums,left,right,center);
  21. 21
  22. 22 int i = left+1;
  23. 23 int j= right-1;
  24. 24 while (i < j){
  25. 25 while (nums[i++] >= nums[center] && i < center){
  26. 26 i++;
  27. 27 }
  28. 28 while (nums[j--] < nums[center] && j > center){
  29. 29 j--;
  30. 30 }
  31. 31
  32. 32 if(nums[i] <= pivot && pivot <= nums[j]){
  33. 33 swap(nums,i,j);
  34. 34 if(i == center){
  35. 35 center = j;
  36. 36 }else if(j == center){
  37. 37 center = i;
  38. 38 }
  39. 39 }
  40. 40 }
  41. 41 if(k <= center){
  42. 42 quickSort(nums,left,center,k);
  43. 43 }else if(k > center){
  44. 44 quickSort(nums,center+1,right,k);
  45. 45 }
  46. 46
  47. 47
  48. 48 }
  49. 49
  50. 50 private int chosePivot(int[] nums,int left,int right,int center){
  51. 51 if(nums[right] > nums[center]){
  52. 52 swap(nums,right,center);
  53. 53
  54. 54 }
  55. 55 if(nums[left] < nums[right]){
  56. 56 swap(nums,left,right);
  57. 57
  58. 58 }
  59. 59
  60. 60 if(nums[left] < nums[center]){
  61. 61 swap(nums,left,center);
  62. 62 }
  63. 63
  64. 64
  65. 65 return nums[center];
  66. 66
  67. 67 }
  68. 68
  69. 69 private void swap(int[] nums,int left,int right){
  70. 70 int temp = nums[left];
  71. 71 nums[left] = nums[right];
  72. 72 nums[right] = temp;
  73. 73 }
  74. 74
  75. 75 public static void main(String[] args){
  76. 76 int[] nums = new int[]{3,2,1,5,6,4};
  77. 77
  78. 78 QuickSort sort = new QuickSort();
  79. 79
  80. 80
  81. 81 System.out.println(sort.findKthLargest(nums,2));
  82. 82 for (int i: nums){
  83. 83 System.out.print(i);
  84. 84 }
  85. 85 }
  86. 86
  87. 87
  88. 88 }

后续会在继续考虑优化问题,展示先这样了

转载于:https://www.cnblogs.com/Kaithy-Rookie/p/11305385.html

发表评论

表情:
评论列表 (有 0 条评论,17人围观)

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

相关阅读

    相关 LeetCode 精选50--子集

    根据题意,找到几何中的所有子集,说实话子集是没有什么头绪的,因为如果采用遍历的方法,稍有遗漏不说,代码的嵌套循环层数随着数组大小的增加而增加,想了很久没有头绪后就去看了看评论,