LeetCode_排序_快速选择_中等_215.数组中的第K个最大元素

ゝ一世哀愁。 2023-10-06 18:48 46阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。  
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**示例 1：**  
输入: \[3,2,1,5,6,4\] 和 k = 2  
输出: 5

**示例 2：**  
输入: \[3,2,3,1,2,4,5,5,6\] 和 k = 4  
输出: 4

**提示：**  
1 <= k <= nums.length <= 104  
\-104 <= nums\[i\] <= 104

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array

## 2.思路 ##

（1）基于简单交换排序的选择方法  
可以考虑利用**简单交换排序**的特点，即每完成一趟排序，就至少会有一个元素的位置确定，那么只需要对数组 nums 进行 k 躺降序排序，此时的 nums\[k - 1\] 必为数组 nums 中第 k 个最大的元素，将其返回即可。

（2）基于快速排序的选择方法  
思路参考[本题官方题解][Link 1]。

（3）基于堆排序的选择方法  
思路参考[本题官方题解][Link 1]。

## 3.代码实现（Java） ##

//思路1————基于简单交换排序的选择方法
    class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            for (int i = 0; i < k; i++) {
        
                for (int j = i + 1; j < nums.length; j++) {
        
                    if (nums[i] < nums[j]) {
        
                        int tmp = nums[i];
                        nums[i] = nums[j];
                        nums[j] = tmp;
                    }
                }
            }
            return nums[k - 1];
        }
    }

//思路2————基于快速排序的选择方法
    class Solution {
        
        Random random = new Random();
        
        //基于快速排序的快速选择
        public int findKthLargest(int[] nums, int k) {
        
            //当前的快速排序是升序排序，故第 K 个最大元素其实就是排序后的元素 nums[nums.length - k]
            return quickSelect(nums, 0, nums.length - 1, nums.length - k);
        }
        
        public int quickSelect(int[] nums, int left, int right, int index) {
        
            int q = randomPartition(nums, left, right);
            if (q == index) {
        
                //当前划分的下标 q 等于 index，则说明这次划分操作后已经找到了第 K 个最大元素，其下标为 q，直接返回 nums[q] 即可
                return nums[q];
            } else {
        
                /*
                    当前划分的下标 q 不等于 index: 
                    (1) 如果 q < index，那么则说明第 K 个最大元素在右区间，此时递归右区间；
                    (2) 如果 q > index，那么则说明第 K 个最大元素在左区间，此时递归左区间；
                */
                return q < index ? quickSelect(nums, q + 1, right, index) : quickSelect(nums, left, q - 1, index);
            }
        }
        
        public int randomPartition(int[] nums, int left, int right) {
        
            // random.nextInt(int num): 随机返回一个 [0, num) 内的整数
            int i = random.nextInt(right - left + 1) + left;
            int tmp = nums[i];
            nums[i] = nums[left];
            nums[left] = tmp;
            return partition(nums, left, right);
        }
        
        //以 nums[left] 为基准，进行一趟划分并返回最终元素 nums[left] 所在的下标
        private int partition(int[] nums, int left, int right) {
        
            int i = left, j = right;
            //以 nums[left] 为基准
            int benchmark = nums[left];
            while (i < j) {
        
                //从右向左扫描，找到一个小于 benchmark 的元素 nums[j]
                while (i < j && benchmark <= nums[j]) {
        
                    j--;
                }
                nums[i] = nums[j];
                //从左向右扫描，找到一个大于 benchmark 的元素 nums[i]
                while (i < j && nums[i] <= benchmark) {
        
                    i++;
                }
                nums[j] = nums[i];
            }
            nums[i] = benchmark;
            return i;
        }
    }

//思路3————基于推排序的选择方法
    //(1) 直接使用已有 API，即 PriorityQueue
    class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            //小顶堆，堆顶是最小元素(优先级队列的底层是用堆实现的)
            PriorityQueue<Integer> queue = new PriorityQueue<>();
            for (int num : nums) {
        
                //在队尾插入元素
                queue.offer(num);
                //堆中元素多余 k 个时，删除堆顶元素
                if (queue.size() > k) {
        
                    //获取队头元素并删除
                    queue.poll();
                }
            }
            return queue.peek();
        }
    }
    
    //(2) 手动实现堆排序
    class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            int length = nums.length;
            //循环建立初始堆，调用 sift 算法 ⌊n / 2⌋ 次
            for (int i = (length - 1) / 2; i >= 0; i--) {
        
                sift(nums, i, length - 1);
            }
            for (int i = length - 1; i >= length - k; i--) {
        
                //将 nums[i] 与根 nums[0] 交换
                int tmp = nums[0];
                nums[0] = nums[i];
                nums[i] = tmp;
                //对 nums[0...i - 1] 进行筛选，得到 i 个节点的堆
                sift(nums, 0, i - 1);
            }
            return nums[length - k];
        }
    
        //对 nums[low...high] 进行筛选，使得以 nums[low] 为根节点的左子树和右子树均为大根堆
        public void sift(int[] nums, int low, int high) {
        
            // nums[j] 是 nums[i] 的左孩子
            int i = low;
            int j = (i == 0) ? 1 : 2 * i;
            int tmp = nums[i];
            while (j <= high) {
        
                //如果右孩子更大，则将 j 指向右孩子
                if (j < high && nums[j] < nums[j + 1]) {
        
                    j++;
                }
                //根节点小于最大孩子节点
                if (tmp < nums[j]) {
        
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    i = j;
                    j = 2 * i;
                } else {
        
                    //如果跟节点大于等于最大孩子关键字，筛选结束
                    break;
                }
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/kth-largest-element-in-an-array/solution/shu-zu-zhong-de-di-kge-zui-da-yuan-su-by-leetcode-/