数组中的第 K 个最大元素

1. 问题描述

1.1 题目定义

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

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

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

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

示例：

输入: nums = [3,2,1,5,6,4], k = 2
输出: 5
解释: 排序后数组为 [6,5,4,3,2,1]，第2大元素是5

输入: nums = [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
解释: 排序后数组为 [6,5,5,4,3,3,2,2,1]，第4大元素是4

1.2 约束条件

• 1 <= k <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

1.3 核心思想

这是一个经典的选择问题（Selection Problem），目标是在未排序的数组中找到第k大的元素，而不需要对整个数组进行完全排序。

2. 解法分析

2.1 解法概览

方法	时间复杂度	空间复杂度	优缺点
快速选择	平均O(n)，最坏O(n²)	O(logn)	理论最优，实现复杂
最小堆	O(nlogk)	O(k)	k较小时高效，易实现
排序法	O(nlogn)	O(1)	简单直观，非最优
最大堆	O(n+klogn)	O(n)	k较大时适用

2.2 算法选择策略

• k较小：推荐最小堆方法
• k较大：推荐最大堆或快速选择
• 追求最优时间复杂度：快速选择算法
• 代码简洁性优先：排序法

3. 快速选择算法（推荐）

3.1 算法思路

快速选择算法基于快速排序的分区思想：

1. 选择一个pivot元素
2. 将数组分区：大于pivot的在左，小于pivot的在右
3. 根据pivot位置决定在哪个分区继续查找
4. 递归直到找到第k大元素

3.2 代码实现

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 第k大元素等于第(n-k+1)小元素
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int kSmallest) {
        // 随机化pivot避免最坏情况
        int pivotIndex = left + new Random().nextInt(right - left + 1);
        
        // 分区操作
        pivotIndex = partition(nums, left, right, pivotIndex);
        
        if (kSmallest == pivotIndex) {
            return nums[kSmallest];
        } else if (kSmallest < pivotIndex) {
            return quickSelect(nums, left, pivotIndex - 1, kSmallest);
        } else {
            return quickSelect(nums, pivotIndex + 1, right, kSmallest);
        }
    }
    
    private int partition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        
        // 将pivot移到末尾
        swap(nums, pivotIndex, right);
        
        // 分区：小于pivot的放左边
        int storeIndex = left;
        for (int i = left; i <= right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        
        // 将pivot放到正确位置
        swap(nums, storeIndex, right);
        return storeIndex;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

3.3 三路快排优化版本

public class Solution {
    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 kSmallest) {
        if (left == right) return nums[left];
        
        // 随机选择pivot
        int pivotIndex = left + new Random().nextInt(right - left + 1);
        
        // 三路分区
        int[] partitionResult = threeWayPartition(nums, left, right, pivotIndex);
        int lt = partitionResult[0];  // 小于pivot的右边界
        int gt = partitionResult[1];  // 大于pivot的左边界
        
        if (kSmallest >= lt && kSmallest <= gt) {
            return nums[kSmallest];
        } else if (kSmallest < lt) {
            return quickSelect(nums, left, lt - 1, kSmallest);
        } else {
            return quickSelect(nums, gt + 1, right, kSmallest);
        }
    }
    
    // 三路分区：[left, lt-1] < pivot, [lt, gt] = pivot, [gt+1, right] > pivot
    private int[] threeWayPartition(int[] nums, int left, int right, int pivotIndex) {
        int pivot = nums[pivotIndex];
        swap(nums, pivotIndex, right);
        
        int lt = left;      // 小于pivot区域的右边界+1
        int gt = right;     // 大于pivot区域的左边界-1
        int i = left;       // 当前处理位置
        
        while (i <= gt) {
            if (nums[i] < pivot) {
                swap(nums, lt++, i++);
            } else if (nums[i] > pivot) {
                swap(nums, i, gt--);
            } else {
                i++;
            }
        }
        
        return new int[]{lt, gt};
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

3.4 迭代版本（避免递归栈溢出）

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int left = 0, right = nums.length - 1;
        int kSmallest = nums.length - k;
        
        while (left <= right) {
            int pivotIndex = partition(nums, left, right);
            
            if (pivotIndex == kSmallest) {
                return nums[pivotIndex];
            } else if (pivotIndex > kSmallest) {
                right = pivotIndex - 1;
            } else {
                left = pivotIndex + 1;
            }
        }
        
        return -1; // 不应该到达这里
    }
    
    private int partition(int[] nums, int left, int right) {
        // 随机选择pivot
        int pivotIndex = left + new Random().nextInt(right - left + 1);
        int pivot = nums[pivotIndex];
        
        // 将pivot移到末尾
        swap(nums, pivotIndex, right);
        
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivot) {
                swap(nums, storeIndex++, i);
            }
        }
        
        swap(nums, storeIndex, right);
        return storeIndex;
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

4. 最小堆方法

4.1 算法思路

维护一个大小为k的最小堆：

1. 遍历数组，将前k个元素加入堆
2. 对于后续元素，如果大于堆顶，则替换堆顶
3. 最终堆顶就是第k大元素

4.2 代码实现

import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 最小堆，保持大小为k
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (heap.size() < k) {
                heap.offer(num);
            } else if (num > heap.peek()) {
                heap.poll();
                heap.offer(num);
            }
        }
        
        return heap.peek();
    }
}

4.3 优化版本

import java.util.PriorityQueue;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(k + 1);
        
        for (int num : nums) {
            heap.offer(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }
        
        return heap.peek();
    }
}

5. 最大堆方法

5.1 算法思路

1. 将所有元素构建成最大堆
2. 执行k次弹出操作
3. 第k次弹出的元素就是答案

5.2 代码实现

import java.util.PriorityQueue;
import java.util.Collections;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 最大堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        
        // 构建堆
        for (int num : nums) {
            heap.offer(num);
        }
        
        // k次弹出
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = heap.poll();
        }
        
        return result;
    }
}

5.3 原地堆化优化

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 原地构建最大堆
        buildMaxHeap(nums);
        
        // k-1次提取最大值
        int heapSize = nums.length;
        for (int i = 0; i < k - 1; i++) {
            swap(nums, 0, --heapSize);
            maxHeapify(nums, 0, heapSize);
        }
        
        return nums[0];
    }
    
    private void buildMaxHeap(int[] nums) {
        for (int i = nums.length / 2 - 1; i >= 0; i--) {
            maxHeapify(nums, i, nums.length);
        }
    }
    
    private void maxHeapify(int[] nums, int i, int heapSize) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < heapSize && nums[left] > nums[largest]) {
            largest = left;
        }
        
        if (right < heapSize && nums[right] > nums[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            swap(nums, i, largest);
            maxHeapify(nums, largest, heapSize);
        }
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

6. 排序方法

6.1 直接排序

import java.util.Arrays;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

6.2 部分排序优化

import java.util.Arrays;

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 降序排序
        Integer[] numsObj = new Integer[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsObj[i] = nums[i];
        }
        
        Arrays.sort(numsObj, (a, b) -> b - a);
        return numsObj[k - 1];
    }
}

7. 复杂度分析详解

7.1 时间复杂度对比

算法	最好情况	平均情况	最坏情况	说明
快速选择	O(n)	O(n)	O(n²)	随机化可避免最坏情况
最小堆	O(nlogk)	O(nlogk)	O(nlogk)	k较小时很高效
最大堆	O(n+klogn)	O(n+klogn)	O(n+klogn)	k较大时适用
排序法	O(nlogn)	O(nlogn)	O(nlogn)	稳定性能

7.2 空间复杂度对比

算法	空间复杂度	说明
快速选择	O(logn)	递归栈深度
最小堆	O(k)	堆存储空间
最大堆	O(n)	存储所有元素
排序法	O(1)	原地排序

7.3 实际性能测试

public class PerformanceTest {
    public static void main(String[] args) {
        int[] testSizes = {1000, 10000, 100000};
        int[] kValues = {1, 10, 100, 1000};
        
        for (int n : testSizes) {
            for (int k : kValues) {
                if (k > n) continue;
                
                int[] nums = generateRandomArray(n);
                
                long start = System.nanoTime();
                int result1 = quickSelectSolution(nums.clone(), k);
                long time1 = System.nanoTime() - start;
                
                start = System.nanoTime();
                int result2 = heapSolution(nums.clone(), k);
                long time2 = System.nanoTime() - start;
                
                System.out.printf("n=%d, k=%d: QuickSelect=%dns, Heap=%dns%n", 
                                n, k, time1, time2);
            }
        }
    }
    
    private static int[] generateRandomArray(int n) {
        Random rand = new Random();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = rand.nextInt(10000);
        }
        return nums;
    }
    
    // 实现各种解法...
}

8. 边界情况处理

8.1 测试用例

public class TestKthLargest {
    public static void main(String[] args) {
        Solution solution = new Solution();
        
        // 测试用例1：基本情况
        int[] nums1 = {3, 2, 1, 5, 6, 4};
        assert solution.findKthLargest(nums1, 2) == 5;
        
        // 测试用例2：有重复元素
        int[] nums2 = {3, 2, 3, 1, 2, 4, 5, 5, 6};
        assert solution.findKthLargest(nums2, 4) == 4;
        
        // 测试用例3：k=1（最大元素）
        int[] nums3 = {7, 10, 4, 3, 20, 15};
        assert solution.findKthLargest(nums3, 1) == 20;
        
        // 测试用例4：k=n（最小元素）
        int[] nums4 = {1, 2, 3, 4, 5};
        assert solution.findKthLargest(nums4, 5) == 1;
        
        // 测试用例5：单元素数组
        int[] nums5 = {1};
        assert solution.findKthLargest(nums5, 1) == 1;
        
        // 测试用例6：所有元素相同
        int[] nums6 = {2, 2, 2, 2, 2};
        assert solution.findKthLargest(nums6, 3) == 2;
        
        // 测试用例7：负数
        int[] nums7 = {-1, -3, 2, 0, -2};
        assert solution.findKthLargest(nums7, 2) == 0;
        
        System.out.println("所有测试用例通过！");
    }
}

8.2 边界条件检查

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 边界检查
        if (nums == null || nums.length == 0) {
            throw new IllegalArgumentException("数组不能为空");
        }
        
        if (k <= 0 || k > nums.length) {
            throw new IllegalArgumentException("k值超出有效范围");
        }
        
        // 特殊情况优化
        if (nums.length == 1) {
            return nums[0];
        }
        
        if (k == 1) {
            return Arrays.stream(nums).max().getAsInt();
        }
        
        if (k == nums.length) {
            return Arrays.stream(nums).min().getAsInt();
        }
        
        // 主要算法逻辑
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    // ... 其他方法实现
}

9. 相关变种问题

9.1 第K小元素

public class Solution {
    public int findKthSmallest(int[] nums, int k) {
        return quickSelect(nums, 0, nums.length - 1, k - 1);
    }
    
    // 快速选择实现...
}

9.2 前K大元素

import java.util.*;

public class Solution {
    public int[] topKLargest(int[] nums, int k) {
        // 方法1：最小堆
        PriorityQueue<Integer> heap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            if (heap.size() < k) {
                heap.offer(num);
            } else if (num > heap.peek()) {
                heap.poll();
                heap.offer(num);
            }
        }
        
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = heap.poll();
        }
        
        return result;
    }
    
    // 方法2：快速选择 + 分区
    public int[] topKLargestQuickSelect(int[] nums, int k) {
        int kthLargest = findKthLargest(nums, k);
        
        List<Integer> result = new ArrayList<>();
        for (int num : nums) {
            if (num >= kthLargest) {
                result.add(num);
            }
        }
        
        return result.stream().mapToInt(i -> i).toArray();
    }
}

9.3 数据流中的第K大元素

LeetCode 703：

import java.util.PriorityQueue;

class KthLargest {
    private PriorityQueue<Integer> heap;
    private int k;
    
    public KthLargest(int k, int[] nums) {
        this.k = k;
        this.heap = new PriorityQueue<>(k);
        
        for (int num : nums) {
            add(num);
        }
    }
    
    public int add(int val) {
        if (heap.size() < k) {
            heap.offer(val);
        } else if (val > heap.peek()) {
            heap.poll();
            heap.offer(val);
        }
        
        return heap.peek();
    }
}

9.4 两个排序数组的第K大元素

public class Solution {
    public int findKthLargest(int[] nums1, int[] nums2, int k) {
        int m = nums1.length, n = nums2.length;
        
        // 转换为第(m+n-k+1)小元素
        return findKthSmallest(nums1, nums2, m + n - k + 1);
    }
    
    private int findKthSmallest(int[] nums1, int[] nums2, int k) {
        if (nums1.length > nums2.length) {
            return findKthSmallest(nums2, nums1, k);
        }
        
        int m = nums1.length, n = nums2.length;
        int left = Math.max(0, k - n);
        int right = Math.min(k, m);
        
        while (left < right) {
            int cut1 = (left + right) / 2;
            int cut2 = k - cut1;
            
            int left1 = cut1 == 0 ? Integer.MIN_VALUE : nums1[cut1 - 1];
            int left2 = cut2 == 0 ? Integer.MIN_VALUE : nums2[cut2 - 1];
            
            int right1 = cut1 == m ? Integer.MAX_VALUE : nums1[cut1];
            int right2 = cut2 == n ? Integer.MAX_VALUE : nums2[cut2];
            
            if (left1 <= right2 && left2 <= right1) {
                return Math.max(left1, left2);
            } else if (left1 > right2) {
                right = cut1 - 1;
            } else {
                left = cut1 + 1;
            }
        }
        
        return -1;
    }
}

10. 性能优化技巧

10.1 快速选择优化

public class OptimizedQuickSelect {
    private static final int INSERTION_SORT_THRESHOLD = 10;
    private Random random = new Random();
    
    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 kSmallest) {
        // 小数组使用插入排序
        if (right - left + 1 <= INSERTION_SORT_THRESHOLD) {
            insertionSort(nums, left, right);
            return nums[kSmallest];
        }
        
        // 三数取中选择pivot
        int pivotIndex = medianOfThree(nums, left, right);
        
        // 三路分区
        int[] partitionResult = threeWayPartition(nums, left, right, pivotIndex);
        int lt = partitionResult[0];
        int gt = partitionResult[1];
        
        if (kSmallest >= lt && kSmallest <= gt) {
            return nums[kSmallest];
        } else if (kSmallest < lt) {
            return quickSelect(nums, left, lt - 1, kSmallest);
        } else {
            return quickSelect(nums, gt + 1, right, kSmallest);
        }
    }
    
    private int medianOfThree(int[] nums, int left, int right) {
        int mid = left + (right - left) / 2;
        
        if (nums[left] > nums[mid]) swap(nums, left, mid);
        if (nums[mid] > nums[right]) swap(nums, mid, right);
        if (nums[left] > nums[mid]) swap(nums, left, mid);
        
        return mid;
    }
    
    private void insertionSort(int[] nums, int left, int right) {
        for (int i = left + 1; i <= right; i++) {
            int key = nums[i];
            int j = i - 1;
            
            while (j >= left && nums[j] > key) {
                nums[j + 1] = nums[j];
                j--;
            }
            
            nums[j + 1] = key;
        }
    }
    
    // ... 其他辅助方法
}

10.2 内存优化

public class MemoryOptimizedSolution {
    // 使用对象池减少GC压力
    private static final ThreadLocal<int[]> TEMP_ARRAY = 
        ThreadLocal.withInitial(() -> new int[1000]);
    
    public int findKthLargest(int[] nums, int k) {
        // 小数组直接处理
        if (nums.length <= 100) {
            return simpleSort(nums, k);
        }
        
        // 大数组使用快速选择
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int simpleSort(int[] nums, int k) {
        int[] temp = TEMP_ARRAY.get();
        if (temp.length < nums.length) {
            temp = new int[nums.length];
            TEMP_ARRAY.set(temp);
        }
        
        System.arraycopy(nums, 0, temp, 0, nums.length);
        Arrays.sort(temp, 0, nums.length);
        
        return temp[nums.length - k];
    }
    
    // ... 快速选择实现
}

11. 实际应用场景

11.1 排行榜系统

public class LeaderBoard {
    private PriorityQueue<Integer> topK;
    private int k;
    
    public LeaderBoard(int k) {
        this.k = k;
        this.topK = new PriorityQueue<>(k);
    }
    
    public void addScore(int score) {
        if (topK.size() < k) {
            topK.offer(score);
        } else if (score > topK.peek()) {
            topK.poll();
            topK.offer(score);
        }
    }
    
    public int getKthHighestScore() {
        return topK.isEmpty() ? -1 : topK.peek();
    }
    
    public List<Integer> getTopKScores() {
        List<Integer> result = new ArrayList<>(topK);
        result.sort(Collections.reverseOrder());
        return result;
    }
}

11.2 推荐系统

public class RecommendationSystem {
    public List<Item> getTopKRecommendations(List<Item> items, int k) {
        // 使用最小堆维护TopK推荐
        PriorityQueue<Item> heap = new PriorityQueue<>(k, 
            Comparator.comparingDouble(Item::getScore));
        
        for (Item item : items) {
            if (heap.size() < k) {
                heap.offer(item);
            } else if (item.getScore() > heap.peek().getScore()) {
                heap.poll();
                heap.offer(item);
            }
        }
        
        List<Item> result = new ArrayList<>(heap);
        result.sort((a, b) -> Double.compare(b.getScore(), a.getScore()));
        return result;
    }
    
    static class Item {
        private String id;
        private double score;
        
        // 构造函数和getter方法...
        public double getScore() { return score; }
    }
}

11.3 性能监控

public class PerformanceMonitor {
    private PriorityQueue<Double> worstKResponses;
    private int k;
    
    public PerformanceMonitor(int k) {
        this.k = k;
        this.worstKResponses = new PriorityQueue<>(k);
    }
    
    public void recordResponseTime(double responseTime) {
        if (worstKResponses.size() < k) {
            worstKResponses.offer(responseTime);
        } else if (responseTime > worstKResponses.peek()) {
            worstKResponses.poll();
            worstKResponses.offer(responseTime);
        }
    }
    
    public double getKthWorstResponseTime() {
        return worstKResponses.isEmpty() ? 0.0 : worstKResponses.peek();
    }
    
    public boolean isPerformanceAcceptable(double threshold) {
        return getKthWorstResponseTime() <= threshold;
    }
}

12. 常见错误与调试

12.1 常见错误

1. 索引转换错误：第k大 ≠ 第k小，注意转换关系
2. 边界条件遗漏：未处理k越界、数组为空等情况
3. pivot选择不当：固定选择导致最坏时间复杂度
4. 堆大小控制错误：最小堆大小超过k或未正确维护
5. 重复元素处理：未考虑相同元素的影响

12.2 调试技巧

public class DebugHelper {
    public static void debugQuickSelect(int[] nums, int k) {
        System.out.println("原数组: " + Arrays.toString(nums));
        System.out.println("查找第 " + k + " 大元素");
        
        // 验证答案
        int[] sorted = nums.clone();
        Arrays.sort(sorted);
        int expected = sorted[sorted.length - k];
        System.out.println("期望答案: " + expected);
        
        // 测试各种算法
        testQuickSelect(nums.clone(), k, expected);
        testHeapMethod(nums.clone(), k, expected);
        testSortMethod(nums.clone(), k, expected);
    }
    
    private static void testQuickSelect(int[] nums, int k, int expected) {
        long start = System.nanoTime();
        int result = new QuickSelectSolution().findKthLargest(nums, k);
        long time = System.nanoTime() - start;
        
        System.out.printf("快速选择: 结果=%d, 正确=%b, 耗时=%dns%n", 
                         result, result == expected, time);
    }
    
    private static void testHeapMethod(int[] nums, int k, int expected) {
        long start = System.nanoTime();
        int result = new HeapSolution().findKthLargest(nums, k);
        long time = System.nanoTime() - start;
        
        System.out.printf("堆方法: 结果=%d, 正确=%b, 耗时=%dns%n", 
                         result, result == expected, time);
    }
    
    private static void testSortMethod(int[] nums, int k, int expected) {
        long start = System.nanoTime();
        int result = new SortSolution().findKthLargest(nums, k);
        long time = System.nanoTime() - start;
        
        System.out.printf("排序方法: 结果=%d, 正确=%b, 耗时=%dns%n", 
                         result, result == expected, time);
    }
    
    // 可视化分区过程
    public static void visualizePartition(int[] nums, int pivot) {
        System.out.println("分区前: " + Arrays.toString(nums));
        System.out.println("Pivot: " + pivot);
        
        // 执行分区
        int pivotIndex = partition(nums, 0, nums.length - 1, pivot);
        
        System.out.println("分区后: " + Arrays.toString(nums));
        System.out.println("Pivot位置: " + pivotIndex);
        System.out.println("左侧(小于pivot): " + 
                          Arrays.toString(Arrays.copyOfRange(nums, 0, pivotIndex)));
        System.out.println("右侧(大于等于pivot): " + 
                          Arrays.toString(Arrays.copyOfRange(nums, pivotIndex + 1, nums.length)));
    }
    
    private static int partition(int[] nums, int left, int right, int pivot) {
        // 分区实现...
        return -1;
    }
}

12.3 单元测试

import org.junit.Test;
import static org.junit.Assert.*;

public class KthLargestTest {
    private Solution solution = new Solution();
    
    @Test
    public void testBasicCases() {
        assertEquals(5, solution.findKthLargest(new int[]{3,2,1,5,6,4}, 2));
        assertEquals(4, solution.findKthLargest(new int[]{3,2,3,1,2,4,5,5,6}, 4));
    }
    
    @Test
    public void testBoundaryConditions() {
        // 单元素
        assertEquals(1, solution.findKthLargest(new int[]{1}, 1));
        
        // k=1（最大值）
        assertEquals(6, solution.findKthLargest(new int[]{3,2,1,5,6,4}, 1));
        
        // k=n（最小值）
        assertEquals(1, solution.findKthLargest(new int[]{3,2,1,5,6,4}, 6));
    }
    
    @Test
    public void testDuplicateElements() {
        assertEquals(2, solution.findKthLargest(new int[]{2,2,2,2,2}, 3));
        assertEquals(3, solution.findKthLargest(new int[]{1,2,2,3,3,3}, 2));
    }
    
    @Test
    public void testNegativeNumbers() {
        assertEquals(0, solution.findKthLargest(new int[]{-1,-3,2,0,-2}, 2));
        assertEquals(-1, solution.findKthLargest(new int[]{-1,-3,-2}, 1));
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void testInvalidK() {
        solution.findKthLargest(new int[]{1,2,3}, 0);
    }
    
    @Test(expected = IllegalArgumentException.class)
    public void testKTooLarge() {
        solution.findKthLargest(new int[]{1,2,3}, 4);
    }
}

13. 面试要点总结

13.1 核心考点

1. 算法选择：能否选择最优的O(n)快速选择算法
2. 实现细节：分区函数的正确实现，边界条件处理
3. 优化思路：随机化、三路快排、迭代版本等优化
4. 复杂度分析：时间和空间复杂度的准确分析
5. 变种扩展：相关问题的举一反三能力

13.2 面试回答模板

1. 问题理解：
   - 这是一个选择问题，目标是找到第k大元素
   - 不需要完全排序，可以用更高效的算法

2. 解法分析：
   - 快速选择：O(n)平均时间，基于分治思想
   - 最小堆：O(nlogk)，当k较小时很高效
   - 排序法：O(nlogn)，简单但非最优

3. 最优解实现：
   - 选择快速选择算法
   - 随机化pivot避免最坏情况
   - 三路分区处理重复元素

4. 复杂度：
   - 时间：平均O(n)，最坏O(n²)
   - 空间：O(logn)递归栈

5. 优化和扩展：
   - 迭代版本、小数组插入排序
   - 相关变种问题的解法

13.3 常见面试问题

1. 为什么快速选择比排序更优？

   • 快速选择只需要部分有序，平均O(n)时间
   • 排序需要完全有序，至少O(nlogn)时间

2. 如何避免快速选择的最坏情况？

   • 随机化pivot选择
   • 三数取中法
   • 三路分区处理重复元素

3. 什么时候选择堆方法？

   • k相对较小时（k << n）
   • 需要在线处理数据流时
   • 内存受限的场景

4. 如何处理重复元素？

   • 使用三路分区
   • 正确处理等于pivot的元素

14. 总结

14.1 核心要点

1. 问题本质：选择问题，不需要完全排序
2. 最优解法：快速选择算法，平均O(n)时间复杂度
3. 实用解法：最小堆方法，O(nlogk)时间，k较小时很高效
4. 关键优化：随机化、三路分区、迭代实现

14.2 算法选择指南

• 追求最优性能：快速选择算法
• 代码简洁性：排序方法
• k较小场景：最小堆方法
• k较大场景：最大堆或快速选择
• 在线数据流：维护最小堆

14.3 学习建议

1. 掌握基础：理解选择问题的本质
2. 重点突破：熟练实现快速选择算法
3. 灵活应用：根据场景选择合适的方法
4. 扩展思维：掌握相关变种问题的解法

数组中的第K个最大元素是算法面试中的高频题目，它不仅考查基本的算法实现能力，更重要的是考查对时间复杂度的理解和算法选择的判断力。通过深入理解这个问题，可以为解决更复杂的选择和排序问题打下坚实基础。