Tìm Phần Tử Thứ k Lớn Nhất Trong Một Mảng Bằng JavaScript

Để tìm phần tử thứ k lớn nhất trong một mảng trong JavaScript, bạn có thể sử dụng phương pháp Quickselect. Quickselect là một thuật toán hiệu quả cho bài toán tìm k-th smallest (hoặc largest) element và có độ phức tạp trung bình là O(n).

Mã Nguồn:

function partition(arr, left, right) {
    let pivot = arr[right];
    let i = left;

    for (let j = left; j < right; j++) {
        if (arr[j] <= pivot) {
            [arr[i], arr[j]] = [arr[j], arr[i]];
            i++;
        }
    }
    [arr[i], arr[right]] = [arr[right], arr[i]];
    return i;
}

function quickSelect(arr, left, right, k) {
    if (left <= right) {
        let pivotIndex = partition(arr, left, right);

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

function findKthLargest(arr, k) {
    let indexToFind = arr.length - k;
    return quickSelect(arr, 0, arr.length - 1, indexToFind);
}

// Ví dụ kiểm tra
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

Giải Thích:

1. Partition Function:

   • Mục Đích: Chia mảng thành hai phần dựa trên một giá trị pivot. Các phần tử nhỏ hơn pivot sẽ nằm bên trái, và các phần tử lớn hơn hoặc bằng pivot sẽ nằm bên phải.
   • Cách Thức: Chọn phần tử cuối cùng làm pivot, sau đó di chuyển các phần tử nhỏ hơn pivot sang bên trái và các phần tử lớn hơn pivot sang bên phải.

2. QuickSelect Function:

   • Mục Đích: Tìm k-th smallest element bằng cách sử dụng thuật toán chia để trị.
   • Cách Thức: Sử dụng hàm partition để tìm vị trí pivot và so sánh vị trí này với k. Tùy thuộc vào kết quả so sánh, hàm tiếp tục tìm kiếm trong phần bên trái hoặc bên phải của mảng.

3. FindKthLargest Function:

   • Mục Đích: Chuyển đổi từ k-th largest element sang k-th smallest element bằng cách tính indexToFind.
   • Cách Thức: indexToFind được tính bằng arr.length - k để chuyển từ phần tử lớn nhất thứ k sang phần tử nhỏ nhất thứ indexToFind.

Tổng Quan:

• Quickselect: Một phiên bản của QuickSort, chuyên dùng để tìm k-th smallest hoặc largest element.
• Độ Phức Tạp Thời Gian: Trung bình O(n), trong trường hợp xấu nhất O(n^2), nhưng có thể cải thiện bằng cách chọn pivot tốt hơn.

Ví Dụ Thực Tế:

console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // 4

Trong ví dụ trên, phần tử lớn thứ 2 trong mảng [3, 2, 1, 5, 6, 4] là 5, và phần tử lớn thứ 4 trong mảng [3, 2, 3, 1, 2, 4, 5, 5, 6] là 4.