215. 数组中的第K个最大元素

要解决这个问题，需要设计一个时间复杂度为O(n)的算法来找到数组中第k个最大的元素。虽然严格O(n)的算法有BFPRT（中位数的中位数算法），但实现复杂。在实际应用中，随机化的快速选择算法的期望时间复杂度为O(n)，且实现更简单，通常能满足要求。

解法：随机化快速选择算法

这个算法基于快速排序的分治思想，但只处理包含目标元素的那部分子数组：

import java.util.Random;

class Solution {
    private Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        // 转换为找第(n-k)小的元素
        return quickSelect(nums, 0, n - 1, n - k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) {
            return nums[left];
        }

        // 随机选择pivot并分区
        int pivotIndex = randomPartition(nums, left, right);

        if (k == pivotIndex) {
            return nums[k];
        } else if (k < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, k);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, k);
        }
    }

    private int randomPartition(int[] nums, int left, int right) {
        // 随机选择pivot
        int randomIndex = left + random.nextInt(right - left + 1);
        swap(nums, randomIndex, right);

        return partition(nums, left, right);
    }

    private int partition(int[] nums, int left, int right) {
        int pivot = nums[right];
        int i = left;

        for (int j = left; j < right; j++) {
            if (nums[j] <= pivot) {
                swap(nums, i, j);
                i++;
            }
        }

        swap(nums, i, right);
        return i;
    }

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

算法解析

1. 问题转换：将"找第k个最大元素"转换为"找第(n-k)小的元素"（n为数组长度）
2. 快速选择：
   • 随机选择一个pivot（基准值）
   • 将数组分为两部分：小于等于pivot的元素在左，大于pivot的元素在右
   • 根据pivot的位置与目标位置k的关系，决定在左半部分还是右半部分继续查找
3. 随机化：随机选择pivot可以避免最坏情况，使算法在期望情况下达到O(n)的时间复杂度

复杂度分析

• 时间复杂度：O(n)（期望时间复杂度）
  • 每次分区操作O(n)
  • 由于随机化，每次能将问题规模减半，总复杂度为n + n/2 + n/4 + ... = O(n)
• 空间复杂度：O(log n)（递归栈的深度）

优化

数组中有较多重复数字时，跳过相关数字下标。

class Solution {
    private Random random = new Random();

    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickP(nums, 0, n - 1, n - k);
    }

    public int quickP(int[] nums, int left, int right, int k) {
        while (left < right) {
            if (left == right) {
                return nums[left];
            }

            // 随机选择pivot
            int pivotIndex = left + random.nextInt(right - left + 1);
            int pivotValue = nums[pivotIndex];

            int lt = left;
            int i = left;
            int gt = right;

            while (i <= gt) {
                if (nums[i] < pivotValue) {
                    swap(nums, i, lt);
                    i++;
                    lt++;
                } else if (nums[i] > pivotValue) {
                    swap(nums, i, gt);
                    gt--;
                } else {
                    i++;
                }
            }

            if (k < lt) {
                right = lt - 1;
            } else if (k > gt) {
                left = gt + 1;
            } else {
                return nums[k];
            }
        }
        return nums[left];

    }

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

堆排序

使用最小堆来维护k个最大的元素。

• 时间复杂度：O(n log k)
• 空间复杂度：O(k)

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();

    for (int num : nums) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // 移除最小元素
        }
    }

    return minHeap.peek(); // 堆顶即为第k大元素
}