LeetCode75-215-Kth-Largest

🧠 Summary of Thoughts

Key Observations

1. You don’t need to fully sort the array
2. The problem is essentially:
   • Find the element at index n - k (0-based sorted order)

Common Approaches

1. Sorting:

   • Sort the array
   • Return nums[n - k]
   • Time: O(n log n)

2. Min Heap:

   • Maintain a min heap of size k (PriorityQueue is a min heap by default)
   • Keep only the k largest elements
   • The top of heap = answer

   Why it works:

   • Always remove the smallest → keep largest k elements
   • Time: O(n log k)
   • Space: O(k)

3. Quickselect：

   • Partition-based (like quicksort)
   • Average: O(n)
   • Worst: O(n²)

✅ Code（Java）

1. Sorting

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

2. Min Heap

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