215. Kth Largest Element in an Array
Tags:
Medium
Skills:
Heap
June 24, 2025
04:32 AM
No headings found
Loading content...
Related Posts
Leetcode
No headings found
Related Posts
Leetcode
Problem
Bài toán yêu cầu tìm phần tử lớn thứ k trong array chưa được sắp xếp
Approach 1 - MinHeap
- Duy trì một min-heap với kích thước k. Duyệt qua mảng, mỗi làn thêm phần tử vào heap, nếu heap vượt quá k phần tử thì loại bỏ phần tử nhỏ nhất. Kết thúc, phần tử ở đỉnh heap là kết quả
- TC: O(nlogk)
- Phù hợp khi n rất lớn và k nhỏ hơn nhiều so với n
Solution
typescripttypescript
1function findKthLargest(nums: number[], k: number): number {
2 const min_heap = new MinPriorityQueue<number>();
3 for (const num of nums) {
4 min_heap.enqueue(num);
5 if (min_heap.size() > k) min_heap.dequeue()
6 }
7
8 return min_heap.front()
9};Approach 2 - Quick select
- Sử dụng thuật toán quick select để tìm phần tử lớn thứ k mà không cần sắp xếp toàn bộ mảng.
- TC trung bình O(n), trường hợp xấu nhất là O(n^2), nhưng thực tế thường rất nhanh
Solution
typescripttypescript
1function findKthLargest(nums: number[], k: number): number {
2 return quickSelect(nums, 0, nums.length - 1, nums.length - k)
3};
4
5function quickSelect(nums: number[], left: number, right: number, k: number): number {
6 if (left === right) return nums[left];
7 const pivot_idx = partition(nums, left, right);
8 if (pivot_idx === k) return nums[pivot_idx]
9 else if (pivot_idx < k) return quickSelect(nums, pivot_idx + 1, right, k)
10 else return quickSelect(nums, left, pivot_idx - 1, k)
11}
12
13function partition(nums: number[], left: number, right: number): number {
14 const pivot = nums[right];
15 let i = left;
16 for (let j = left; j < right; j++) {
17 if (nums[j] <= pivot) {
18 [nums[i], nums[j]] = [nums[j], nums[i]]
19 i++
20 }
21 }
22 [nums[i], nums[right]] = [nums[right], nums[i]]
23 return i;
24} 💡
Quick select?
Quick select là một biến thể của quick sort, được tối ưu hóa để tìm kiếm phần tử thứ k trong một mảng chưa sắp xếp mà không cần phải sắp xếp toàn bộ mảng.
Nguyên lý hoạt động
- Chọn pivot (phần tử chốt)
- Chọn một phần tử bất kỳ trong mảng làm pivot (thường là đầu, cuối, giữa hoặc ngẫu nhiên)
- Phân hoạch (partition)
- Sắp xếp lại mảng sao cho
- Các phần tử lớn hơn pivot nằm một bên
- Các phần tử nhỏ hơn pivot nằm bên còn lại
- Pivot ở đúng vị trí của nó nếu mảng được sắp xếp
- So sánh vị trí pivot với k
- Nếu vị trí pivot đúng bằng vị trí cần tìm (k), return về pivot
- Nếu
k < pivot, tiếp tục tìm kiểm ở nửa bên trái (các phần tử nhỏ hơn pivot) - Nếu
k > pivot, tiếp tục tìm kiếm ở nửa bên phải (các phần tử lớn hơn pivot)
Quá trình này lặp lại (đệ quy hoặc lặp) cho đến khi tìm được phần tử đúng vị trí k.