Next Permutation

Q: Độ phức tạp thời gian của hoán vị kế tiếp là gì?

O(n) . Một lượt duyệt từ phải sang trái sẽ tìm điểm xoay, lượt thứ hai tìm giá trị để hoán đổi, rồi đảo ngược một lần để sắp xếp lại hậu tố. Bộ nhớ bổ sung là O(1) , vì mọi thao tác đều diễn ra bên trong mảng.

Trung bìnhMảng và chuỗi Hai con trỏ

+10

Bạn nhận được một mảng (array) số nguyên nums, các giá trị có thể lặp lại. Hãy hình dung tất cả các cách sắp xếp khác nhau của những giá trị này, được xếp theo thứ tự từ điển: so sánh hai cách sắp xếp tại chỉ số đầu tiên mà chúng khác nhau, cách có giá trị nhỏ hơn ở đó sẽ đứng trước. Trả về cách sắp xếp đứng ngay sau nums theo thứ tự đó.

Nếu nums đã là cách sắp xếp lớn nhất, thì không có cách nào đứng sau nó: hãy trả về cách nhỏ nhất, tức là các giá trị được sắp xếp theo thứ tự tăng dần. Cố gắng đạt thời gian O(n) và bộ nhớ bổ sung O(1).

Hàm

nextPermutation(nums: integer-array) → integer-array

numsinteger-array: cách sắp xếp các giá trị hiện tại
Trả vềinteger-array: sắp xếp tiếp theo theo thứ tự từ điển, hoặc các giá trị được sắp xếp theo thứ tự tăng dần nếu nums là lớn nhất

Ràng buộc

1 ≤ nums.length ≤ 5000
0 ≤ nums[i] ≤ 1000

Ví dụ

Đầu vào: nums = [2, 5, 4, 1]
Đầu ra: [4, 1, 2, 5]
Giải thích: Đuôi 5, 4, 1 đang giảm, nên số 2 đứng trước nó phải tăng lên. Giá trị nhỏ nhất trong đuôi lớn hơn 2 là 4; đặt 2 vào vị trí đó rồi sắp xếp phần còn lại theo thứ tự tăng dần: [4, 1, 2, 5].

Đầu vào: nums = [3, 2, 2, 1]
Đầu ra: [1, 2, 2, 3]
Giải thích: Cả mảng đang giảm dần, nên đây là cách sắp xếp lớn nhất của 3, 2, 2 và 1. Đáp án vòng lại thành cách sắp xếp nhỏ nhất, [1, 2, 2, 3].

Đầu vào: nums = [1, 5, 1]
Đầu ra: [5, 1, 1]
Giải thích: Số 1 đầu tiên phải tăng lên. Số 1 cuối cùng bằng số đó, không lớn hơn, nên giá trị duy nhất có thể thay thế nó là 5, tạo thành [5, 1, 1].

Câu hỏi mở rộng

Làm thế nào để bạn tìm cách sắp xếp trước đó, cách sắp xếp đứng ngay trước nums theo thứ tự từ điển?

Lời giải

Hậu tố giảm dần đã lớn nhất có thể với các giá trị của nó, nên cách sắp xếp tiếp theo sẽ thay đổi giá trị ngay trước hậu tố đó, tức là điểm xoay. Tăng điểm xoay lên một lượng nhỏ nhất có thể, rồi làm cho hậu tố nhỏ nhất có thể. Cách này cần hai lượt quét từ bên phải và một lần đảo ngược ngay trong mảng.

Sắp xếp danh sách theo thứ tự

Đúng, nhưng không chạy xong với các test lớn nhất

Ý tưởng

Tạo các cách sắp xếp theo chiều sâu từ các giá trị đã sắp xếp, luôn thử giá trị chưa dùng nhỏ nhất trước. Cách này tạo ra chúng theo thứ tự từ điển, vì vậy cách đầu tiên lớn hơn nghiêm ngặt so với nums là đáp án; nếu không có cách nào như vậy, trả về các giá trị đã sắp xếp. Các giá trị lặp lại tạo ra một số cách sắp xếp hai lần, như 115, 151, 115, 151, 511, 511 với [1, 1, 5], nhưng một bản sao chỉ lặp lại cách đã tạo trước đó, vì vậy cách lớn hơn đầu tiên vẫn là cách tiếp theo.

Số lượng tăng theo n!: 12 giá trị phân biệt có 479,001,600 cách sắp xếp.

Thuật toán

Sắp xếp một bản sao của nums vào pool.
Xây dựng các cách sắp xếp theo chiều sâu, chọn các phần tử chưa dùng trong pool từ trái sang phải.
Khi hoàn thành một cách sắp xếp, so sánh với nums theo từng vị trí.
Trả về cách sắp xếp đầu tiên lớn hơn nums.
Nếu không có cách nào lớn hơn, trả về pool.

def nextPermutation(nums):
    n = len(nums)
    pool = sorted(nums)  # taking the smallest unused value first gives sorted order
    used = [False] * n
    current = []

    def build():
        # True once current holds the first arrangement greater than nums
        if len(current) == n:
            return current > nums  # Python compares lists in dictionary order
        for i in range(n):
            if not used[i]:
                used[i] = True
                current.append(pool[i])
                if build():
                    return True
                current.pop()
                used[i] = False
        return False

    if build():
        return current
    return pool  # nothing is greater: nums was the largest arrangement

Tìm điểm xoay, đổi chỗ, đảo ngược hậu tố

Ý tưởng

Điểm trụ là giá trị đầu tiên tính từ bên phải nhỏ hơn phần tử bên phải nó: số 2 trong [2, 5, 4, 1]. Đây là vị trí ngoài cùng bên phải có thể tăng lên, và việc tăng vị trí ngoài cùng bên phải có thể tăng sẽ giúp mức tăng nhỏ nhất.

Đổi chỗ điểm trụ với giá trị nhỏ nhất ở hậu tố lớn hơn điểm trụ. Hậu tố giảm dần, nên đó là giá trị lớn hơn điểm trụ nằm ngoài cùng bên phải: số 4, tạo thành [4, 5, 2, 1]. Hậu tố vẫn giảm dần, vì điểm trụ cũ vừa với vị trí của số 4. Khi phần đầu đã lớn hơn, hậu tố cần nhỏ nhất có thể, theo thứ tự tăng dần, và đảo ngược một dãy giảm dần sẽ làm được điều đó: [4, 1, 2, 5].

Nếu không có điểm trụ, mảng đang ở cách sắp xếp lớn nhất, và đảo ngược toàn bộ mảng sẽ tạo ra cách sắp xếp nhỏ nhất. Mỗi bước chỉ cần một lượt duyệt hoặc một lần đảo ngược: thời gian O(n) và bộ nhớ O(1), dù phiên bản R trả về một bản sao O(n).

Thuật toán

Đặt i thành n-2 rồi di chuyển nó sang trái khi nums[i] ≥ nums[i + 1].
Nếu i ≥ 0, đặt j thành n-1 rồi di chuyển nó sang trái khi nums[j] ≤ nums[i], sau đó đổi chỗ nums[i] và nums[j].
Đảo ngược phần từ i + 1 đến cuối bằng hai chỉ số di chuyển về phía nhau.
Trả về nums.

def nextPermutation(nums):
    n = len(nums)
    # 1. the pivot is the last index whose value is smaller than the next one
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2. swap it with the rightmost value that is larger than it
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 3. the suffix after the pivot is falling: reverse it to make it rising
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1
    return nums

Lỗi thường gặp và trường hợp biên

Dùng > thay vì ≥ khi tìm chốt. Trong [3, 2, 2, 1], cặp 2, 2 không phải là một bước tăng, và dừng ở đó sẽ chọn một chốt không thể tăng lên.
Đổi chỗ với một giá trị bằng chốt. Trong [1, 5, 1], đổi chỗ hai số 1 không làm thay đổi gì; hãy tìm một giá trị lớn hơn hẳn.
Đổi chỗ với giá trị lớn nhất trong hậu tố. Trong [2, 5, 4, 1], cách đó đưa 5 lên đầu và bỏ qua mọi cách sắp xếp bắt đầu bằng 4.
Bỏ qua trường hợp không có chốt. Cách sắp xếp lớn nhất phải quay về thứ tự đã sắp xếp bằng cách đảo ngược toàn bộ mảng.
Trong Rust, chỉ số usize bắt đầu từ n-2 sẽ gây panic khi n = 1, còn lùi qua 0 sẽ gây panic khi không có chốt. Hãy dùng chỉ số có dấu hoặc đếm từ 1.

Câu hỏi thường gặp3

Độ phức tạp thời gian của hoán vị kế tiếp là gì?

O(n). Một lượt duyệt từ phải sang trái sẽ tìm điểm xoay, lượt thứ hai tìm giá trị để hoán đổi, rồi đảo ngược một lần để sắp xếp lại hậu tố. Bộ nhớ bổ sung là O(1), vì mọi thao tác đều diễn ra bên trong mảng.

Tại sao bạn đảo ngược hậu tố thay vì sắp xếp nó?

Sau khi hoán đổi, hậu tố vẫn đang giảm dần, nên đảo ngược nó sẽ sắp xếp các phần tử theo thứ tự tăng dần. Đảo ngược mất O(n); sắp xếp cho kết quả tương tự trong O(n log n).

Next Permutation có hoạt động với các giá trị trùng lặp không?

Đúng, miễn là cả hai phép so sánh đều xem các giá trị bằng nhau là không lớn hơn. Khi tìm pivot, ta bỏ qua các phần tử liền kề bằng nhau bằng ≥, còn khi tìm phần tử để đổi chỗ, ta bỏ qua các giá trị bằng pivot bằng ≤. Sau đó, [1, 5, 1] trở thành [5, 1, 1], cách sắp xếp khác biệt tiếp theo.

def nextPermutation(nums):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Kiểm thử #3

Đối số

nums = [2, 5, 4, 1]

Đầu ra mong đợi

[4, 1, 2, 5]