讨论/《中级算法》 - 数组中的第K个最大元素/
《中级算法》 - 数组中的第K个最大元素

利用快速排序的 Partition 方法来查找第 k 大的元素,平均时间复杂度 O(n),空间复杂度 O(1)

快速排序的 Partition 方法可以固定数组中一个中枢元素的位置,并将小于该中枢值的元素放置于中枢元素左边,大于中枢值的元素放置于中枢元素的右边

利用该性质,我们可以使用双指针对数组进行中枢元素的位置查找,若查找到的中枢元素索引恰好为 nums.length - k,即查找到了数组中第 k 大的元素。(第 k 大的元素,即是第 nums.length - k + 1 小的元素,下标即为 nums.length - k)

同时在 Partition 中使用随机数选取 key(中枢值),平均情况下可认为是数组的中间值,则外部循环可看似二分查找,每次只需对一半的区间进行 Partition 操作

故平均时间复杂度为 O(n),最坏时间复杂度为 O(n^2), 空间复杂度为 O(1)

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int index = nums.length - k;
        return findKthMininum(nums, 0, nums.length - 1, index);
    }

    private int findKthMininum(int[] nums, int start, int end, int k) {
        if (k < start || k > end) {
            throw new IllegalArgumentException();
        }
        // binary search
        while (start < end) {
            // quick sort's partition to find pivot
            int pivot = partition(nums, start, end);
            if (pivot == k) {
                return nums[k];
            } else if (pivot < k) {
                start = pivot + 1;
            } else {
                end = pivot - 1;
            }
        }
        return nums[start];
    }

    private int partition(int[] nums, int start, int end) {
        int random = new Random().nextInt(end - start);
        swap(nums, start, random + start);
        int key = nums[start];
        while (start < end) {
            while (start < end && nums[end] >= key) {
                end--;
            }
            nums[start] = nums[end];
            while (start < end && nums[start] <= key) {
                start++;
            }
            nums[end] = nums[start];
        }
        nums[start] = key;
        return start;
    }

    private void swap(int[] nums, int x, int y) {
        int temp = nums[x];
        nums[x] = nums[y];
        nums[y] = temp;
    }
}
展开全部 8 讨论