E hèm, như đã nói ở post trước, tối nay mình sẽ start luôn, vì goal của mình là để ôn lại kiến thức, nên không được badge cũng không sao (mình start hơi trễ, tận ngày 16)

Start thôi =)))

URL: https://leetcode.com/explore/featured/card/january-leetcoding-challenge-2021/581/week-3-january-15th-january-21st/3606/

Đề như sau:


Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: You may assume k is always valid, 1 ≤ k ≤ array's length.


Nhìn chung thì đề khá dễ, chỉ là tìm element index thứ k trong mảng unsort thôi. Nhưng mà mới bắt đầu thì dễ vậy cho đỡ nản =)))

Ý tưởng: sort array, sau đó lấy phần tử thứ k. Xong.

Đầu tiên, phải chọn ngôn ngữ đã, mình thì cả năm rồi toàn code JS, nhưng mình cảm giác JS nó cứ chầm chậm. Thôi quất luôn C++, vì đằng nào cũng học 4 năm đại học, không lẽ quên nhanh vậy...

Implement Sorting

Hmm, nhắc đến sorting thì có rất nhiều algorithm: bubble sort, merge sort, quick sort,... Tùy vào yêu cầu mà ta sẽ chọn các loại giải thuật sort khác nhau. Mình chưa kịp load lại não là nên dùng giải thuật sort nào, cơ mà mình thích gì đó nhanh nhanh, vì thế mình sẽ chọn quick sort.

Search google quicksort c++ vector implementation, xong bỏ vô code, vậy là xong. Giờ chỉ việc get phần tử thứ k là xong :triump:

Get the kth element

Đơn giản là return nums[k-1] là xong :)

Run -> FAILED

What???, vì trong đề có yêu cầu là kth largest element, nhưng lúc search thì mình không để ý là quick sort theo order như thế nào. Và may mắn cho mình là nó đang theo order tăng dần -> Toang.

Mình quá lười để implement lại quicksort theo order giảm dần, vậy nên mình sẽ thay đổi giá trị k :)))

Run -> Accepted (Yeahhh)

Code

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        // sort array
        quicksort(nums, 0, nums.size() - 1);
        // since I am too lazy to change quick sort to descending order
        // -> I will change the value of k :)
        int nth = nums.size() - k;

        return nums[nth];
    }
    
    
    void quicksort(vector<int> &values, int left, int right) {
        if(left < right) {
            int pivotIndex = partition(values, left, right);
            quicksort(values, left, pivotIndex - 1);
            quicksort(values, pivotIndex, right);
        }
    }

    int partition(vector<int> &values, int left, int right) {
        int pivotIndex = left + (right - left) / 2;
        int pivotValue = values[pivotIndex];
        int i = left, j = right;
        int temp;
        while(i <= j) {
            while(values[i] < pivotValue) {
                i++;
            }
            while(values[j] > pivotValue) {
                j--;
            }
            if(i <= j) {
                temp = values[i];
                values[i] = values[j];
                values[j] = temp;
                i++;
                j--;
            }
        }
        return i;
    }

};

Result https://i.imgur.com/3d5ymke.png


received_2309471779196344.jpeg

By Toàn Hồ