【CT】LeetCode手撕—215. 数组中的第K个最大元素

题目

• 原题连接：215. 数组中的第K个最大元素

1-思路

• 1- TopN 问题，使用优先级队列。创建时自定义比较规则
  • 记：优先级队列的自定义比较规则如何创建？
• 2- 通过遍历将 数组存入小根堆
• 3- pop小根堆 k 次，堆顶元素就是第 k 大

1-1 思路1 使用优先级队列实现（不推荐）

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 利用 优先级队列实现一个 排序好的小根堆

        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2) -> o2-o1);

        for(int i:nums){
            pq.add(i);
        }
        
        int res = 0;
        for(int j = 0 ; j < k;j++){
            res = pq.poll();
        }

        return res;
    }
}

1-2 ⭐思路2 手撕小顶堆

• 参考学习视频：https://www.bilibili.com/video/BV1fp4y1D7cj/?spm_id_from=333.880.my_history.page.click&vd_source=f0cc9fb393ea8368ee6e72359708d425

① 堆的 结点的性质

• ① 下标为 i 结点的父节点下标： (i-1)/2 代表下标为i 的父节点的下标
• ② 下标为 i 结点的左孩子节点下标：i*2 + 1 代表下标为i 的左孩子结点下标
• ③ 下标为 i 结点的右孩子节点下标：i*2 + 2 代表下标为i 的左孩子结点下标
• ④ 二叉树性质：大小为 n 个元素的的二叉树中第一个非叶子结点的下标为 n / 2 - 1

② ⭐维护堆的性质 heapify ——时间复杂度 O(logn)

• 小顶堆维护
  • 如果当前结点的值 不是 左孩子、右孩子 三者中最小的，此时就将最小的元素的值调换到当前位置。
    

/**
 * 维护 堆的性质
 * @param nums 数组
 * @param n 数组长度
 * @param i 当前结点 i
 */
public static void heapify(int[] nums,int n ,int i){
    int min = i;
    int lson = 2*i+1;
    int rson = 2*i+2;
    // 1- 找出最大节点的下标
    if(lson<n && nums[lson] < nums[min]){
        min = lson;
    }
    if(rson<n && nums[rson] < nums[min]){
        min = rson;
    }
    // 2- 根据下标 交换结点
    if(min != i){
        swap(nums,i,min);
        // 递归交换其孩子
        heapify(nums,n,min);
    }
}

③ ⭐建堆+堆排 heapSort(int[] nums,int n)

建堆

• i 从 n/2-1 开始，对每个 i 进行 heapify 操作，进行建堆

堆排

    /**
     *
     * @param nums 数组
     * @param n 长度 n
     */
    public static void heapSort(int[] nums,int n){
        // 1- 从非叶子结点开始遍历，维护堆的性质
        for(int i = n/2-1 ; i>=0 ; i--){
            heapify(nums,n,i);
        }

        // 2- 排序
        for(int i =n-1;i>0;i--){
            swap(nums,i,0);
            heapify(nums,i,0);
        }
    }

2- 实现

⭐215. 数组中的第K个最大元素——题解思路

class Solution {
public int findKthLargest(int[] nums, int k) {
// 根据输入的数组 实现堆化
heapSort(nums,nums.length);
return nums[k-1];
}
public void heapify(int[] nums,int n ,int i){
int min = i;
int lson = i*2+1;
int rson = i*2+2;
// 找最小
if(lson<n && nums[lson] < nums[min]){
min = lson;
}
if(rson<n && nums[rson] < nums[min]){
min = rson;
}
if(i!=min){
// 交换
swap(nums,i,min);
// 递归堆化
heapify(nums,n,min);
}
}
public void swap(int[] nums,int i ,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
// 建堆 + 堆排
public void heapSort(int[] nums,int n){
// 建堆
for(int i = n/2 -1;i>=0;i--){
heapify(nums,n,i);
}
// 排序
for(int i = n-1;i>0;i--){
swap(nums,i,0);
heapify(nums,i,0);
}
}
}

3- ACM实现

public class findKthLargest {
/**
* 维护 堆的性质
* @param nums 数组
* @param n 数组长度
* @param i 当前结点 i
*/
public static void heapify(int[] nums,int n ,int i){
int min = i;
int lson = 2*i+1;
int rson = 2*i+2;
// 1- 找出最大节点的下标
if(lson<n && nums[lson] < nums[min]){
min = lson;
}
if(rson<n && nums[rson] < nums[min]){
min = rson;
}
// 2- 根据下标 交换结点
if(min != i){
swap(nums,i,min);
// 递归交换其孩子
heapify(nums,n,min);
}
}
public static void swap(int[] nums,int i ,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
/**
*
* @param nums 数组
* @param n 长度 n
*/
public static void heapSort(int[] nums,int n){
// 1- 从非叶子结点开始遍历，维护堆的性质
for(int i = n/2-1 ; i>=0 ; i--){
heapify(nums,n,i);
}
// 2- 排序
for(int i =n-1;i>0;i--){
swap(nums,i,0);
heapify(nums,i,0);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("输入数组长度");
int n = sc.nextInt();
int[] nums = new int[n];
System.out.println("输入数组");
for(int i = 0 ; i < n;i++){
nums[i] = sc.nextInt();
}
heapSort(nums,n);
System.out.println("输入你要读取的 第 k 大的数");
int k = sc.nextInt();
System.out.println(nums[k-1]);
}
}