Giải Thuật Leetcode 31 Sắp Xếp Tiếp Theo Từ Điển - tin tức the thao bóng đá

Mar 6, 2025 · 5 phút đọc · tin tức the thao bóng đá ·

Đề bài của bài toán này có phần dễ gây hiểu lầm vì không giải thích rõ ràng về thứ tự từ điển. Mặc dù nó đúng với định nghĩa thông thường của thứ tự từ điển, nhưng cách trình bày trong đề bài có thể khiến người đọc nhầm lẫn. Chúng ta sẽ phân tích bài toán một cách chi tiết hơn để làm rõ các quy luật.

Thứ tự từ điển ở đây được xem xét theo hướng từ trái sang phải, giống như khi tra cứu trong từ điển hoặc so sánh các chuỗi ký tự theo mặc định. Ví dụ, khi so sánh hai dãy số, chúng ta so từng chữ số lần lượt từ trái qua phải. Nếu các chữ số tại cùng một vị trí giống nhau, chúng ta tiếp tục so sánh chữ số tiếp theo. Chẳng hạn:

11 đứng trước 12, và 12 lại đứng trước 13.
Với cùng một tập hợp chữ số, ví dụ top kiến tạo ngoại hạng anh 2025 như 12, chỉ có hai cách sắp xếp là 12 và 21. Theo thứ tự từ điển, 12 đứng trước 21.

Từ đó, chúng ta có thể rút ra một vài quy luật. Hãy xem xét ví dụ cụ thể hơn với ba chữ số: 123. Các hoán vị của dãy này bao gồm:

Nhìn vào bảng trên, ta thấy rằng:

Khi chữ số đầu tiên giống nhau (chẳng hạn 123 và 132), thì 132 đứng sau 123.
Quy luật tổng quát là: dãy tăng dần luôn là nhỏ nhất, và dãy giảm dần luôn là lớn nhất.

Với ba chữ số, chúng ta có thể chia bài toán thành hai phần:

Tìm phần tử đầu tiên từ cuối dãy mà không thuộc chuỗi giảm dần.
Đảo chỗ phần tử này với phần tử lớn nhất trong chuỗi giảm dần ngay phía sau nó, rồi sắp xếp lại phần còn lại theo thứ tự tăng dần.

Phân Tích Chi Tiết Qua Ví Dụ

Chúng ta hãy xem xét ví dụ cụ thể: 1 4 6 5 3 2.

Bước 1: Tìm Phần Tử Đầu Tiên Không Thuộc Chuỗi Giảm Dần

Trong dãy này, chuỗi giảm dần từ cuối lên là 6 5 3 2. Phần tử đầu tiên không thuộc chuỗi giảm dần chính là 4.

Bước 2: Tìm Phần Tử Lớn Hơn Nhưng Gần Nhất

Sau khi xác định được 4, ta cần tìm phần tử lớn hơn 4 nhưng gần nhất trong chuỗi giảm dần phía sau. Trong trường hợp này, phần tử đó là 5.

Bước 3: Hoán Đổi Hai Phần Tử

Hoán đổi 4 và 5, ta thu được dãy mới:

11 5 6 4 3 2

Bước 4: Sắp Xếp Lại Phần Sau Theo Thứ Tự Tăng Dần

Phần phía sau 5 vẫn đang ở dạng giảm dần (6 4 3 2). Để đảm bảo dãy mới là thứ tự tiếp theo gần nhất, ta cần sắp xếp lại phần này theo thứ tự tăng dần:

11 5 2 3 4 6

Xử Lý Trường Hợp Đặc Biệt

Có hai trường hợp ngoại lệ cần lưu ý:

Dãy ban đầu đã hoàn toàn giảm dần: Trong trường hợp này, dãy tiếp theo sẽ là dãy tăng dần đầu tiên. Ví dụ, nếu dãy ban đầu là 6 5 4 3 2 1, thì dãy tiếp theo sẽ là 1 2 3 4 5 6.
Dãy ban đầu hoàn toàn tăng dần: Trường hợp này thực chất cũng tương tự như trên. Ta chỉ cần hoán đổi hai phần tử cuối cùng.

Mã Nguồn Thực Hiện

Dưới đây là đoạn mã Java để thực hiện thuật toán này:

 1public void nextPermutation(int[] nums) {
 2    int n = nums.length;
 3    int i = n - 2;
 4
 5    // Tìm phần tử đầu tiên từ cuối mà không thuộc chuỗi giảm dần
 6    while (i >= 0 && nums[i] >= nums[i + 1]) {
 7        i--;
 8    }
 9
10    if (i >= 0) {
11        // Tìm phần tử lớn nhất [tin tức the thao bóng đá](/post/86bc44283d5b75d2.html)  nhưng gần nhất trong chuỗi giảm dần phía sau
12        int j = n - 1;
13        while (nums[j] <= nums[i]) {
14            j--;
15        }
16        // Hoán đổi hai phần tử
17        swap(nums, i, j);
18    }
19
20    // Sắp xếp lại phần phía sau theo thứ tự tăng dần
21    reverse(nums, i + 1, n - 1);
22}
23
24private void swap(int[] nums, int i, int j) {
25    int temp = nums[i];
26    nums[i] = nums[j];
27    nums[j] = temp;
28}
29
30private void reverse(int[] nums, int start, int end) {
31    while (start < end) {
32        swap(nums, start, end);
33        start++;
34        end--;
35    }
36}

Tổng Kết

Thuật toán này hoạt động dựa trên việc tìm kiếm và thay đổi các phần tử sao cho dãy mới là thứ tự tiếp theo gần nhất theo thứ tự từ điển. Cách tiếp cận này đảm bảo hiệu quả cả về mặt thời gian và không gian.

Hy vọng bài viết này giúp bạn hiểu rõ hơn về lịch bóng đá ngoại hạng anh bài toán Next Permutation!