Next Permutation

Q: Berapa kompleksitas waktu Next Permutation?

O(n) . Satu kali pemindaian dari kanan menemukan pivot, pemindaian kedua menemukan nilai yang akan ditukar, dan satu pembalikan memperbaiki sufiks. Memori tambahan adalah O(1) , karena semuanya terjadi di dalam array.

SedangArray dan string Two pointers

+10

Kamu menerima sebuah array bilangan bulat nums, dan nilainya mungkin berulang. Bayangkan semua susunan berbeda dari nilai-nilai ini, diurutkan berdasarkan urutan kamus: bandingkan dua susunan pada indeks pertama yang berbeda, lalu susunan dengan nilai yang lebih kecil di sana berada lebih awal. Kembalikan susunan yang berada tepat setelah nums dalam urutan tersebut.

Jika nums sudah merupakan susunan terbesar, tidak ada susunan setelahnya: kembalikan susunan terkecil, yaitu nilai-nilai yang diurutkan secara menaik. Usahakan waktu O(n) dan memori ekstra O(1).

Fungsi

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

numsinteger-array: susunan nilai saat ini
Mengembalikaninteger-array: susunan berikutnya dalam urutan leksikografis, atau nilai-nilai yang diurutkan dari yang terkecil ke terbesar jika nums adalah yang terbesar

Batasan

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

Contoh

Input: nums = [2, 5, 4, 1]
Output: [4, 1, 2, 5]
Penjelasan: Ekor 5, 4, 1 menurun, jadi 2 di depannya harus bertambah. Nilai ekor terkecil yang lebih besar dari 2 adalah 4. Letakkan di sana dan susun sisanya dalam urutan menaik: [4, 1, 2, 5].

Input: nums = [3, 2, 2, 1]
Output: [1, 2, 2, 3]
Penjelasan: Seluruh array menurun, jadi susunannya adalah yang terbesar dari 3, 2, 2, dan 1. Jawabannya berputar kembali ke susunan terkecil, [1, 2, 2, 3].

Input: nums = [1, 5, 1]
Output: [5, 1, 1]
Penjelasan: Angka 1 yang pertama harus bertambah. Angka 1 yang terakhir sama dengannya, bukan lebih besar, jadi satu-satunya nilai yang bisa menggantikannya adalah 5, sehingga hasilnya [5, 1, 1].

Pertanyaan lanjutan

Bagaimana cara menemukan susunan sebelumnya, yang tepat sebelum nums dalam urutan kamus?

Solusi

Suffix yang menurun sudah sebesar mungkin berdasarkan nilai-nilainya, jadi susunan berikutnya mengubah nilai tepat sebelumnya, yaitu pivot. Naikkan pivot dengan jumlah sekecil mungkin, lalu buat suffix sekecil mungkin. Untuk itu, lakukan dua pemindaian dari kanan dan satu pembalikan di dalam array.

Susunan list secara berurutan

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Bangun susunan secara depth first dari nilai yang sudah diurutkan, selalu coba nilai terkecil yang belum digunakan terlebih dahulu. Cara ini menghasilkan susunan dalam urutan kamus, jadi susunan pertama yang benar-benar lebih besar daripada nums adalah jawabannya; jika tidak ada, kembalikan nilai yang sudah diurutkan. Nilai yang berulang membuat beberapa susunan dibangun dua kali, seperti 115, 151, 115, 151, 511, 511 untuk [1, 1, 5], tetapi salinan hanya mengulangi susunan yang sudah dibangun sebelumnya, jadi susunan lebih besar pertama tetap menjadi susunan berikutnya.

Jumlahnya bertambah sebesar n!: 12 nilai berbeda memiliki 479,001,600 susunan.

Algoritma

Urutkan salinan nums ke dalam pool.
Buat susunan dengan pencarian depth first, pilih entri pool yang belum digunakan dari kiri ke kanan.
Setelah susunan selesai, bandingkan dengan nums posisi demi posisi.
Kembalikan susunan pertama yang lebih besar daripada nums.
Jika tidak ada yang lebih besar, kembalikan 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

Cari pivot, tukar, balikkan sufiks

Intuisi

Pivot adalah nilai pertama dari kanan yang lebih kecil daripada tetangga kanannya: angka 2 dalam [2, 5, 4, 1]. Pivot berada di posisi paling kanan yang masih bisa diperbesar, dan memperbesar posisi paling kanan yang memungkinkan membuat kenaikannya sekecil mungkin.

Tukar pivot dengan nilai suffix terkecil yang lebih besar secara ketat. Suffix tersusun menurun, jadi pilih nilai paling kanan yang lebih besar daripada pivot: 4, sehingga hasilnya [4, 5, 2, 1]. Suffix tetap menurun karena posisi 4 sebelumnya cocok untuk pivot lama. Karena bagian depan kini lebih besar, suffix harus sekecil mungkin, dalam urutan menaik. Membalik urutan yang menurun menghasilkan hal itu: [4, 1, 2, 5].

Jika tidak ada pivot, array sudah dalam susunan terbesar. Membalik seluruh array akan menghasilkan susunan terkecil. Setiap langkah memerlukan satu pemindaian atau satu pembalikan: waktu O(n) dan memori O(1), meskipun versi R mengembalikan salinan O(n).

Algoritma

Tetapkan i ke n-2 dan geser ke kiri selama nums[i] ≥ nums[i + 1].
Jika i ≥ 0, tetapkan j ke n-1 dan geser ke kiri selama nums[j] ≤ nums[i], lalu tukar nums[i] dan nums[j].
Balik bagian dari i + 1 hingga akhir dengan dua indeks yang bergerak saling mendekat.
Kembalikan 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

Jebakan dan kasus tepi

Menggunakan > alih-alih ≥ dalam pencarian pivot. Dalam [3, 2, 2, 1], pasangan 2, 2 bukan kenaikan, dan berhenti di sana memilih pivot yang tidak bisa bertambah.
Menukar dengan nilai yang sama dengan pivot. Dalam [1, 5, 1], menukar kedua angka 1 tidak mengubah apa pun. Cari nilai yang benar-benar lebih besar.
Menukar dengan nilai terbesar di bagian akhir array. Dalam [2, 5, 4, 1], ini menempatkan 5 di depan dan melewati semua susunan yang dimulai dengan 4.
Melewatkan kasus tanpa pivot. Susunan terbesar harus kembali dalam keadaan terurut, dengan membalik seluruh array.
Di Rust, indeks usize yang dimulai dari n-2 menyebabkan panic saat n = 1, dan bergerak ke kiri melewati 0 menyebabkan panic saat tidak ada pivot. Gunakan indeks bertanda atau hitung mulai dari 1.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Next Permutation?

O(n). Satu kali pemindaian dari kanan menemukan pivot, pemindaian kedua menemukan nilai yang akan ditukar, dan satu pembalikan memperbaiki sufiks. Memori tambahan adalah O(1), karena semuanya terjadi di dalam array.

Mengapa kamu membalik urutan sufiks, bukan mengurutkannya?

Setelah pertukaran, sufiksnya masih menurun, jadi membaliknya akan langsung mengurutkan sufiks tersebut dalam urutan menaik. Pembalikan membutuhkan O(n); pengurutan menghasilkan hasil yang sama dalam O(n log n).

Apakah Next Permutation berfungsi dengan nilai duplikat?

Ya, selama kedua perbandingan menganggap nilai yang sama tidak lebih besar. Pencarian pivot melewati tetangga yang sama dengan ≥, dan pencarian pertukaran melewati nilai yang sama dengan pivot dengan ≤. Kemudian [1, 5, 1] menjadi [5, 1, 1], susunan berbeda berikutnya.

def nextPermutation(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [2, 5, 4, 1]

Output yang diharapkan

[4, 1, 2, 5]