• 欢迎光临~

leetcode 215. Kth Largest Element in an Array 数组中的第K个最大元素

开发技术 开发技术 2022-05-21 次浏览

一、题目大意

https://leetcode.cn/problems/kth-largest-element-in-an-array

给定整数数组 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

二、解题思路

理解题意:
在一个未排序的数组中,找到第k大的数字。输入一个数组和一个目标k,输出第k大的数字,题目黑夜一定有解。
解题思路:
快速选择一般用于解决k-th Element问题,可以在O(n)时间复杂度,O(1)空间复杂度完成求解工作。快速选择的实现和快速排序的实现类似,不过只需要找第k大的(pivort)即可,不需要对其进行左右排序。与快速排序一样,快速选择一般需要先打乱数组,否则最坏情况下时间复杂度为O(n^2)。
解决思路:
数组中第k个最大元素其实就是求数组中第nums.length - k个最小元素,我们定义target = nums.length - k。
先找一个中枢点(pivort),然后遍历其他数字,小于pivort的排左边,大于pivort的排右边,中枢点是数组中的第几大的数字就确定了,如果pivort与target相等,直接返回pivort位置的数字,如果大于target,说明要求的数字在左边部分,否则在右边部分。剩下的就是递归了。

三、解题方法

3.1 Java实现

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int l = 0;
        int r = nums.length - 1;
        // 第k个大,就是第nums.length - k个小
        int target = nums.length - k;
        while (l < r) {
            int mid = quickSelection(nums, l, r);
            if (mid == target) {
                return nums[mid];
            }
            if (mid > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return nums[l];
    }

    /**
     * 快速选择
     */
    private int quickSelection(int[] nums, int l, int r) {
        int i = l + 1;
        int j = r;
        while (true) {
            while (i < r && nums[i] <= nums[l]) {
                i++;
            }
            while (l < j && nums[j] >= nums[l]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        swap(nums, l, j);
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

四、总结小记

  • 2022/5/21 理解为什么用快速选择来解决这个问题是关键,重点是要理解快速排序
喜欢 (0)