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

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

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

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

具体思路如下：

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

言归正传：

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

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

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

具体程序如下：

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

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

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