二分查找--215. 数组中的第K个最大元素/medium 理解度B(wait opt)

1、题目

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

 

示例 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 <= 105
  • -104 <= nums[i] <= 104
Related Topics
  • 数组
  • 分治
  • 快速选择
  • 排序
  • 堆(优先队列)

2、题目分析

借助快排的分治思想,找到区间支点,再判断支点所在位置是否为第k大的位置

3、复杂度最优解代码示例

    Integer kNum = null;
    public int findKthLargest(int[] nums, int k) {
        findKth(nums, k, 0, nums.length - 1);
        return kNum == null ? -1 : nums[kNum];
    }
    
    public void findKth(int[] nums, int k, int left, int right) {
        if (kNum != null || left > right) {
            // 退出递归,已找到第k大,或者左指针大于右指针。
            return;
        }
        int leftArgs = left;
        int rightArgs = right;
        // 支点标识:true-支点为左指针,false-支点为右指针
        boolean isLeft = true;
        while (left <= right) {
            if (nums[left] >= nums[right]) {
                // 若左指针数据大于右指针数据,则互换位置,并标识新的支点指针。
                // 注:nums[left] == nums[right] 时,从结果角度看,可不互换。但若不互换,在特殊情况,比如数组元素均相等时,时间复杂度会从O(nlogn)退化为O(n²)
                int temp = nums[right];
                nums[right] = nums[left];
                nums[left] = temp;

                isLeft = !isLeft;
            }
            if (isLeft) {
                // isLeft=true,表明支点为左指针,此时移动右指针
                right--;
            } else {
                // isLeft=false,表明支点为右指针,此时移动左指针
                left++;
            }
        }

        int point = isLeft ? left : right;
        if (point == nums.length - k) {
            // 判断支点是否为第k大,是则不再递归分治。
            kNum = point;
        } else if (point > nums.length - k) {
            // 支点所在位置大于第k大,故第k大在当前支点的左边区间
            findKth(nums, k, leftArgs, point - 1);
        } else {
            // 支点所在位置小于第k大,故第k大在当前支点的右边区间
            findKth(nums, k, point + 1, rightArgs);
        }
    }

4、适用场景

  1. 数据分析:在处理大量数据时,找出第K个最大元素可以帮助我们了解数据的分布情况,例如在销售数据中找出销售额排名第K的商品。

  2. 算法设计:在设计一些需要排序的算法时,如快速排序、堆排序等,找出第K个最大元素可以作为算法的一部分。

  3. 游戏开发:在一些游戏中,可能需要找出得分排名第K的玩家,这时就需要找出数组中的第K个最大元素。

  4. 网络编程:在网络编程中,可能需要找出传输速度排名第K的节点,这时也需要找出数组中的第K个最大元素。

  5. 机器学习:在机器学习中,可能需要找出预测结果排名第K的模型,这时也需要找出数组中的第K个最大元素。

  6. 数据库查询:在数据库查询中,可能需要找出某个字段值排名第K的记录,这时也需要找出数组中的第K个最大元素。

评论
添加红包

请填写红包祝福语或标题

红包个数最小为10个

红包金额最低5元

当前余额3.43前往充值 >
需支付:10.00
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明:

1.余额是钱包充值的虚拟货币,按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载,可以购买VIP、付费专栏及课程。

余额充值