DX's Digital Garden

1._数组中的第k个最大元素

5 min read

  • 3.17

    • 过了一遍小根堆 heap 做法，简单
    • 过了快选，有点东南
      • 没分清找的是目标 index
      • 从 partition 函数收到 pivot 的 index 是已经固定的，然后与目标 index 对比，易出错
      • random 的返回想好

  • 2.15

    • 小根堆秒了
    • 快选
      • 随机 pivotIndex 后确定 pivot，将 pivot 暂存到最右边
      • 声明 storeIndex为 left，开始逐个扫描，小于 pivot 的与 storeIndex 互换，storeIndex 往前走
      • 最后换回pivot 于 storeIndex，这时的 storeIndex 就是 pivot 的位置 （左边都是比他小的）
class Solution {
    Random random = new Random();
    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums,k,0,nums.length-1,nums.length-k);
    }
    public int quickSelect(int[] nums,int k,int left,int right,int index){
        int pivotIndex = partition(nums,k,left,right,index);
        if(pivotIndex==index){
            return nums[pivotIndex];
        }else if(pivotIndex<index){
            return  quickSelect(nums,k,pivotIndex+1,right,index);
        }else{
            return  quickSelect(nums,k,left,pivotIndex-1,index);
        }
    }
    public int partition(int[] nums,int k,int left,int right,int index){
        int pivotIndex = left+random.nextInt(right-left+1);
        int pivot = nums[pivotIndex];
        swap(nums,pivotIndex,right);
        int storeIndex = left;
        for(int i=left;i<right;i++){
            if(nums[i]<pivot){
                swap(nums,i,storeIndex);
                storeIndex++;
            }
        }
        swap(nums,right,storeIndex);
        return storeIndex;
    }
    public void swap(int[] nums,int l,int r){
        int temp = nums[l];
        nums[l] = nums[r];
        nums[r] =temp; 
    }
}

  • 2.2

    • 还有小根堆这种东西的？（PriorityQueue） 纯黑科技啊
    • 第二种快速选择，非常经典
      • 在次主函数中，以已确定的 Index 为锚点，看 target 在哪边，来选择再次选择哪一边
      • 在 partition 函数中，需要保存 pivot 值，

  • 快速选择:快速排序的“精简版”，它只排自己关心的那一半。

class Solution {
    Random rand = new Random();
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        int targetIndex = n-k;//按升序排序,所以是倒的
        return quickSelect(nums,0,n-1,targetIndex);
    }
    public int quickSelect(int[]nums,int left,int right,int targetIndex){
        int pivotIndex=partition(nums,left,right);
        if(pivotIndex==targetIndex){
            return nums[pivotIndex];
        } else if(pivotIndex>targetIndex){
            return quickSelect(nums,left,pivotIndex-1,targetIndex);
        }else{
            return quickSelect(nums,pivotIndex+1,right,targetIndex);
        }
    }
    public int partition(int[]nums,int left,int right){
        int pivotIndex = left+rand.nextInt(right-left+1);
        int pivot = nums[pivotIndex];
        swap(nums,pivotIndex,right);
        //  记录下一个要放小数的位置,当前应放下一个“小于 pivot”的位置,后续用这个与rigth交换回来,当pivotIndex
        int storeIndex = left;
        for(int i=left;i<right;i++){
            if(nums[i]<pivot){
                swap(nums,i,storeIndex);
                storeIndex++;
            }
        }
        //left, storeIndex-1] 都比 pivot 小
        //[storeIndex, right-1] 都比 pivot 大或等于。
        //换回来
        swap(nums,storeIndex,right);
        return storeIndex;
    }
    public void swap(int[] nums,int left,int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
import java.util.Random;
 
class Solution {
    public int[] sortArray(int[] nums) {
        randomizedQuickSort(nums, 0, nums.length - 1);
        return nums;
    }
 
    private void randomizedQuickSort(int[] nums, int left, int right) {
        // 递归结束条件：只有一个元素或没有元素
        if (left >= right) {
            return;
        }
 
        // 1. 分区：算出 pivot 应该在的下标 pos
        int pos = partition(nums, left, right);
 
        // 2. 递归：解决 pivot 左边的乱序
        randomizedQuickSort(nums, left, pos - 1);
 
        // 3. 递归：解决 pivot 右边的乱序
        randomizedQuickSort(nums, pos + 1, right);
    }
 
    private int partition(int[] nums, int left, int right) {
        // 随机化 Pivot (防止最坏情况 O(N^2))
        int randomIndex = left + new Random().nextInt(right - left + 1);
        swap(nums, randomIndex, right);
        
        int pivot = nums[right];
        int i = left; // i 是分界线，i 左边的都 <= pivot
 
        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }
        swap(nums, i, right); // 把 pivot 放回中间
        return i;
    }
 
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
区别点快速排序 (Quicksort)快速选择 (Quickselect)
目标把整个数组排好序只找第 k 大（或第 k 小）元素
递归策略对左右两边都递归只递归包含目标元素的一边
停止条件子数组长度 ≤ 1当 pivot 恰好是第 k 个元素
平均复杂度O(n log n)O(n)
最坏复杂度O(n²)O(n²)（相同退化）
返回值无（原地排序）返回目标值

方法二：最小堆（Heap / PriorityQueue）

import java.util.PriorityQueue;
class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

用一个最小堆保存当前最大的 k 个元素。

  1. 遍历数组；
  2. 将元素放入最小堆；
  3. 当堆的大小超过 k 时，弹出堆顶（最小的那个）；
  4. 遍历结束后，堆顶就是第 k 个最大元素。
  • 时间复杂度： O(n log k)
  • 空间复杂度： O(k) ​ ✅ 当 k ≪ n 时非常高效

Graph View