快速选择算法：为何能在O(n)时间内找到第K大元素？从原理到LeetCode完整通关指南

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        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];
        }
        
        // Hoare分区
        int i = left - 1, j = right + 1;
        int pivot = nums[(left + right) >>> 1];
        
        while (true) {
            do { i++; } while (nums[i] < pivot);
            do { j--; } while (nums[j] > pivot);
            if (i >= j) break;
            swap(nums, i, j);
        }
        
        if (k <= j) {
            return quickSelect(nums, left, j, k);
        }
        return quickSelect(nums, j + 1, right, k);
    }
    
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 统计频率
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.merge(num, 1, Integer::sum);
        }
        
        // 提取频率数组
        int[] freqs = new int[freqMap.size()];
        int idx = 0;
        Map<Integer, Integer> freqToCount = new HashMap<>();
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            freqs[idx] = entry.getValue();
            freqToCount.merge(entry.getValue(), 1, Integer::sum);
            idx++;
        }
        
        // 找第k大的频率
        int kthFreq = findKthLargest(freqs, k);
        
        // 收集结果
        List<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            if (entry.getValue() >= kthFreq) {
                result.add(entry.getKey());
            }
        }
        
        // 可能因为重复频率导致结果超过k个，需要裁剪
        return result.stream().limit(k).mapToInt(i -> i).toArray();
    }
    
    private int findKthLargest(int[] nums, int k) {
        // 同215题实现
        return quickSelect(nums, 0, nums.length - 1, nums.length - k);
    }
    
    private int quickSelect(int[] nums, int left, int right, int k) {
        if (left == right) return nums[left];
        
        int i = left - 1, j = right + 1;
        int pivot = nums[(left + right) >>> 1];
        
        while (true) {
            do { i++; } while (nums[i] < pivot);
            do { j--; } while (nums[j] > pivot);
            if (i >= j) break;
            int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
        }
        
        if (k <= j) return quickSelect(nums, left, j, k);
        return quickSelect(nums, j + 1, right, k);
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        int n = points.length;
        int[] dists = new int[n];
        for (int i = 0; i < n; i++) {
            dists[i] = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        }
        
        quickSelect(dists, 0, n - 1, k - 1);
        
        int threshold = dists[k - 1];
        int[][] result = new int[k][2];
        int idx = 0;
        for (int i = 0; i < n && idx < k; i++) {
            int d = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if (d <= threshold) {
                result[idx++] = points[i];
            }
        }
        return result;
    }
    
    private void quickSelect(int[] nums, int left, int right, int k) {
        if (left >= right) return;
        
        int i = left - 1, j = right + 1;
        int pivot = nums[(left + right) >>> 1];
        
        while (true) {
            do { i++; } while (nums[i] < pivot);
            do { j--; } while (nums[j] > pivot);
            if (i >= j) break;
            int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp;
        }
        
        if (k <= j) {
            quickSelect(nums, left, j, k);
        } else {
            quickSelect(nums, j + 1, right, k);
        }
    }
}

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

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n-1][n-1];
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            int count = countLessEqual(matrix, mid);
            if (count < k) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
    
    private int countLessEqual(int[][] matrix, int target) {
        int n = matrix.length;
        int count = 0;
        int row = n - 1, col = 0;
        
        while (row >= 0 && col < n) {
            if (matrix[row][col] <= target) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }
}