Yêu cầu bài toán

Cho một array và một số nguyên k, trả về phần tử lớn thứ k trong mảng. Ngoài ra bài toán này còn yêu cầu là không được xài sắp xếp.

Quick Select

Quick select là gì?

Quick select là một thuật toán sử dụng trong việc tìm kiếm một phần tử cụ thể trong một danh sách không được sắp xếp. Nó được sử dụng để tìm kiếm phần tử thứ k trong một danh sách gồm n phần tử, trong đó k thường là một số nguyên từ 1 đến n. Quick select dựa trên thuật toán chia để trị, sử dụng nguyên tắc chọn một phần tử chốt (pivot) và chia danh sách thành hai phần, một bên nhỏ hơn pivot và một bên lớn hơn pivot. Dựa vào giá trị k so với vị trí của pivot, thuật toán quyết định tiếp tục tìm kiếm ở phần nào của danh sách.

Cách sử dụng Quick select:

• Chọn một phần tử chốt (pivot) từ danh sách. Thông thường, bạn có thể chọn phần tử ở giữa danh sách, nhưng lưu ý là lựa chọn pivot có thể ảnh hưởng đến hiệu suất của thuật toán.
• Chia danh sách thành hai phần, một phần nhỏ hơn pivot và một phần lớn hơn pivot. Sắp xếp các phần này.
• So sánh vị trí của pivot với giá trị k mà bạn muốn tìm kiếm. Nếu pivot nằm ở vị trí k, bạn đã tìm thấy phần tử cần.
• Nếu k lớn hơn vị trí của pivot, tìm kiếm ở phần danh sách lớn hơn pivot. Nếu k nhỏ hơn vị trí của pivot, tìm kiếm ở phần danh sách nhỏ hơn pivot.
• Lặp lại quá trình này bằng cách thu hẹp phạm vi tìm kiếm cho đến khi bạn tìm thấy phần tử cần tìm.

Triển khai

Ok sau khi tìm hiểu thì chúng ta sẽ code thôi

public class Solution 
{
    private static readonly Random rand = new();
    
    public int FindKthLargest(int[] nums, int k) 
    {
        int result = Select(nums, 0, nums.Length - 1, nums.Length - k);
        return result;
    }

    private int Select(int[] nums, int left, int right, int kSmallest) 
    {
        if (left == right) 
        {
            return nums[left];
        }

        int pivotIndex = rand.Next(left, right);
        pivotIndex = Partition(nums, left, right, pivotIndex);

        if (kSmallest == pivotIndex) 
        {
            return nums[kSmallest];
        } 
        else if (kSmallest < pivotIndex) 
        {
            return Select(nums, left, pivotIndex - 1, kSmallest);
        } 
        else 
        {
            return Select(nums, pivotIndex + 1, right, kSmallest);
        }
    }

    private int Partition(int[] nums, int left, int right, int pivotIndex) 
    {
        int pivot = nums[pivotIndex];
        Swap(nums, pivotIndex, right);
        int storeIndex = left;

        for (int i = left; i <= right; i++) 
        {
            if (nums[i] < pivot) 
            {
                Swap(nums, storeIndex, i);
                storeIndex++;
            }
        }

        Swap(nums, storeIndex, right);
        return storeIndex;
    }

    private void Swap(int[] nums, int a, int b) 
    {
        int tmp = nums[a];
        nums[a] = nums[b];
        nums[b] = tmp;
    }
}

Giải thích

1. Có ai thắc mắc rằng ở trong hàm FindKthLargest, khi gọi hàm Select thì ta phải pass value là nums.Length - k ở param cuối không?
   • Sở dĩ ta pass giá trị nums.Length - k chứ không phải pass k vào là vì ta đang tìm phần tử lớn nhất thứ k chứ không phải phần tử bé nhất thứ k.
   • Chúng ta đang thực hành việc sắp xếp phần tử bé ở bên trái pivot, phần tử lớn ở bên phải pivot. Vậy thì không thể chỉ vì muốn tìm phần tử lớn thứ k mà ta phải đổi cách thực hiện bằng cách đem phần tử bé hơn ở bên phải và phần tử lớn hơn ở bên trái được. Hãy thực hành cho đúng trước rồi khi rành thì muốn biến tấu sao cũng được nha các bạn.
   • Sau khi mình nêu ra 2 quan điểm ở trên, nếu các bạn vẫn chưa hiểu thì lấy 1 tờ giấy ra, viết 1 cái mảng nào đó, chọn 1 phần tử k nào đó được sắp xếp tăng dần và lấy độ dài mảng trừ đi k xem có phải cái kết quả đó chính là phần tử lớn thứ k hay không?
   • Bài toán yêu cầu là tìm phần tử lớn thứ k đúng không? Nhưng suy ra chúng ta cũng có thể dịch ngược yêu cầu của bài toán này thành, tìm phần tử bé thứ nums.Length - k trong mảng để dễ thực hiện với Quick select hơn nha.
2. Có ai thắc mắc rằng ở trong hàm Partition, tại sao ta phải hoán đổi vị trí của pivot với vị trí bên phải ngoài cùng trước khi thực hiện việc phân vùng không?
   • Lý do hoán đổi pivot với phần tử ngoài cùng bên phải khi bắt đầu quá trình phân vùng là để không cho cái thằng pivot bị ảnh hưởng trong quá trình phân vùng.
   • Việc phân vùng ảnh hưởng tới việc di chuyển các phần tử xung quanh trong mảng dựa trên việc chúng nhỏ hơn hay lớn hơn pivot. Nếu pivot nằm ở giữa mảng thì pivot vẫn bị ảnh hưởng, pivot bị di chuyển trong lúc phân vùng -> gây ra phức tạp trong quá trình phân vùng.
   • Di chuyển pivot về phần tử cuối cùng giúp đảm bảo rằng nó vẫn ở nguyên vị trí pivot trong khi những phần tử khác vẫn được sắp xếp. Sau khi phân vùng xong thì sẽ di chuyển pivot lại từ vị trí cuối cùng của nó tới vị trí của storeIndex đang trỏ đến. (Do đó các bạn hiểu storeIndex làm gì ha).