题意整理

  • 给定一个整数数组，找出数组中第 k 大的数。

方法一（利用小顶堆）

1.解题思路

  • 首先定义一个小顶堆。
  • 然后将前k个元素直接加入到小顶堆。
  • 遍历后续每一个元素，如果比堆顶元素大，则可能是前k大的元素，加入小顶堆，并弹出堆顶元素。否则，直接跳过。

2.代码实现

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        //定义一个小顶堆
        PriorityQueue<Integer> queue=new PriorityQueue<>();
        
        for(int i=0;i<n;i++){
            //前K个元素直接加入小顶堆
            if(i<K){
                queue.offer(a[i]);
            }
            else{
                //如果当前元素比堆顶元素大，则加入小顶堆后，移除堆顶元素
                if(queue.peek()<a[i]){
                    queue.offer(a[i]);
                    queue.poll();
                }
            }
            
        }
        
        return queue.peek();
    }
}

3.复杂度分析

  • 时间复杂度：需要遍历数组中所有元素，每次调整堆的时间复杂度为O(log2k)O(log_2k)，所以时间复杂度为O(nlog2k)O(nlog_2k)。
  • 空间复杂度：需要额外大小为k的小顶堆，所以空间复杂度是O(k)O(k)。

方法二（利用快排的partition）

1.解题思路

前置知识：快排的partition函数能找到数组中的一个位置（枢纽值），使得这个位置前的元素大于当前位置元素，这个位置后的元素小于当前位置元素。所以只要找到对应的枢纽值为K-1，则当前位置元素就是第K大的数。

  • 定义左边界为0，右边界为n-1。使用partition函数找到一个分割点，然后让这个分割点不断逼近K-1的位置。
  • 如果大于K-1，则调整右边界，从low到index-1之间继续找。如果小于K-1，则调整左边界，从index+1到high之间继续找。
  • 如果找到，直接结束循环。

图解展示： alt

2.代码实现

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        int low=0;
        int high=n-1;
        //使用partition函数找到分割点，如果在K-1位置，则该位置元素恰好是第k大的数
        int index=partition(a,low,high);
        while(index!=K-1){
            //如果大于K-1，则从low到index-1之间继续找
            if(index>K-1){
                high=index-1;
                index=partition(a,low,high);
            }
            //如果小于K-1，则从index+1到high之间继续找
            else if(index<K-1){
                low=index+1;
                index=partition(a,low,high);
            }
            //如果找到，直接结束循环
            else{
                break;
            }
        }
        return a[index];
    }
    
    private int partition(int[] nums,int low,int high){
        //定义枢纽值
        int pivot=nums[low];
        while(low<high){
            //找到第一个大于pivot的位置
            while(low<high&&nums[high]<=pivot) high--;
            //交换
            swap(nums,low,high);
            //找到第一个小于pivot的位置
            while(low<high&&nums[low]>=pivot) low++;
            //交换
            swap(nums,low,high);
        }
        return low;
    }
    
    //交换low、high对应位置元素的值
    private void swap(int[] nums,int low,int high){
        int temp=nums[low];
        nums[low]=nums[high];
        nums[high]=temp;
    }
}

3.复杂度分析

  • 时间复杂度：partition函数的时间复杂度为O(n)O(n)，需要进行log2nlog_2n次划分，所以时间复杂度为O(nlog2n)O(nlog_2n)。
  • 空间复杂度：需要额外常数级别的空间，所以空间复杂度是O(1)O(1)。