26. 第K大的元素：在一个未排序的数组中找到第K大的元素

PangHu大约 4 分钟

在一个未排序的数组中找到第 K 大的元素是一个常见的算法问题。可以通过多种方法来解决这个问题，包括排序、堆排序、快速选择（Quick Select）等。下面我将介绍几种常见的方法及其实现。

1. 方法一：排序法

最简单的方法是将数组排序，然后直接取第 K 大的元素。

1.1 算法步骤

将数组排序（从大到小或从小到大）。
取排序后数组的第 K 个元素。

1.2 代码实现

import java.util.Arrays;

public class KthLargestElement {

    public int findKthLargest(int[] nums, int k) {
        // 将数组排序
        Arrays.sort(nums);
        // 返回第 K 大的元素
        return nums[nums.length - k];
    }

    public static void main(String[] args) {
        KthLargestElement solution = new KthLargestElement();
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int result = solution.findKthLargest(nums, k);
        System.out.println("The " + k + "th largest element is: " + result);
    }
}

1.3 复杂度分析

时间复杂度：O(n log n)，主要消耗在排序步骤。
空间复杂度：O(1)，不需要额外的存储空间（除了排序可能的开销）。

2. 方法二：基于堆排序的优先队列法

我们可以使用一个大小为 K 的最小堆（优先队列）来存储数组中的前 K 个最大元素，然后堆顶元素就是第 K 大的元素。

2.1 算法步骤

创建一个大小为 K 的最小堆（优先队列）。
遍历数组，将每个元素添加到堆中。
如果堆的大小超过 K，移除堆顶元素。
遍历结束后，堆顶元素即为第 K 大的元素。

2.2 代码实现

import java.util.PriorityQueue;

public class KthLargestElement {

    public int findKthLargest(int[] nums, int k) {
        // 创建一个最小堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll(); // 保持堆的大小为 K
            }
        }

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

    public static void main(String[] args) {
        KthLargestElement solution = new KthLargestElement();
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int result = solution.findKthLargest(nums, k);
        System.out.println("The " + k + "th largest element is: " + result);
    }
}

2.3 复杂度分析

时间复杂度：O(n log k)，遍历数组需要 O(n) 次操作，每次插入堆操作的时间复杂度为 O(log k)。
空间复杂度：O(k)，用于存储最小堆的元素。

3. 方法三：快速选择（Quick Select）

快速选择算法是一种基于快速排序的选择算法，能够在平均 O(n) 的时间复杂度下找到第 K 大的元素。

3.1 算法步骤

选择一个基准元素（pivot），将数组划分为两部分，一部分比基准大，另一部分比基准小。
判断基准的位置与 K 的关系：
- 如果基准的位置正好是第 K 大元素的位置，返回基准元素。
- 如果基准的位置比 K 小，递归地在右子数组中查找。
- 如果基准的位置比 K 大，递归地在左子数组中查找。

3.2 代码实现

public class KthLargestElement {

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

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

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

    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;
    }

    public static void main(String[] args) {
        KthLargestElement solution = new KthLargestElement();
        int[] nums = {3, 2, 1, 5, 6, 4};
        int k = 2;
        int result = solution.findKthLargest(nums, k);
        System.out.println("The " + k + "th largest element is: " + result);
    }
}

3.3 复杂度分析

时间复杂度：O(n) 在平均情况下，最坏情况为 O(n^2)（当划分不平衡时）。
空间复杂度：O(1)，除递归栈外，不需要额外的存储空间。

4. 总结

排序法：简单直接，但时间复杂度较高，为 O(n log n)。
堆排序法：通过维护一个大小为 K 的最小堆，可以在 O(n log k) 的时间内找到第 K 大的元素，适合处理大量数据。
快速选择法：基于快速排序的思想，平均情况下时间复杂度为 O(n)，是最有效的方法之一。

根据具体场景，可以选择不同的方法来实现第 K 大元素的查找。如果对算法的效率要求较高，推荐使用快速选择法；如果数据量较大且无法一次性装入内存，可以考虑使用堆排序法。