Next Permutation

Q: Next Permutation'ın zaman karmaşıklığı nedir?

O(n) . Sağdan yapılan bir tarama pivotu bulur, ikinci tarama takas edilecek değeri bulur ve tek bir ters çevirme soneki düzeltir. Her şey dizinin içinde gerçekleştiğinden ek bellek O(1) 'dir.

OrtaDiziler ve dizgiler İki işaretçi

+10

Sana bir tam sayılar dizisi nums veriliyor ve değerler tekrar edebilir. Bu değerlerin birbirinden farklı her dizilişini sözlük sırasına göre sıralanmış olarak düşün: İki dizilişi farklı oldukları ilk indiste karşılaştır; o indiste daha küçük değere sahip olan önce gelir. Bu sıralamada nums dizisinden hemen sonra gelen dizilişi döndür.

nums zaten en büyük dizilişse, ondan sonra gelen yoktur: değerlerin artan sırada sıralandığı en küçük dizilişi döndür. O(n) zaman ve O(1) ek bellek hedefle.

Fonksiyon

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

numsinteger-array: değerlerin mevcut düzeni
Döndürürinteger-array: sözlük sırasına göre bir sonraki düzenleme veya nums en büyük değerse artan sırada sıralanmış değerler

Kısıtlar

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

Örnekler

Girdi: nums = [2, 5, 4, 1]
Çıktı: [4, 1, 2, 5]
Açıklama: 5, 4, 1 kuyruğu azalan sırada, bu yüzden önündeki 2 büyümeli. 2'den büyük en küçük kuyruk değeri 4'tür; onu oraya koy ve geri kalanını artan sırada yaz: [4, 1, 2, 5].

Girdi: nums = [3, 2, 2, 1]
Çıktı: [1, 2, 2, 3]
Açıklama: Dizinin tamamı azalan sırada olduğundan, 3, 2, 2 ve 1'in en büyük dizilişidir. Yanıt, en küçük diziliş olan [1, 2, 2, 3] ile başa sarar.

Girdi: nums = [1, 5, 1]
Çıktı: [5, 1, 1]
Açıklama: İlk 1 büyümeli. Son 1 ona eşittir, daha büyük değildir; bu nedenle onun yerini alabilecek tek değer 5'tir ve sonuç [5, 1, 1] olur.

Ek soru

Bunun yerine, sözlük sıralamasında nums'tan hemen önce gelen permütasyonu nasıl bulurdunuz?

Çözüm

Azalan bir sonek, değerlerinin izin verdiği ölçüde zaten büyüktür; bu yüzden bir sonraki düzenleme, ondan hemen önceki değeri, yani pivotu değiştirir. Pivotu mümkün olan en küçük miktarda artır, ardından soneki mümkün olduğunca küçük hâle getir. Bunun için sağdan iki tarama ve dizi içinde bir ters çevirme gerekir.

Sıralı liste düzenlemeleri

Doğru, ama en büyük testlerde bitmiyor

Sezgi

Düzenlemeleri sıralanmış değerlerden başlayarak derinlik öncelikli biçimde oluştur ve her zaman önce kullanılmamış en küçük değeri dene. Böylece sözlük sırasına göre elde edilirler; bu nedenle nums değerinden kesin olarak büyük olan ilk düzenleme yanıttır. Böyle bir düzenleme yoksa sıralanmış değerleri döndür. Tekrarlanan değerler bazı düzenlemeleri iki kez oluşturur; örneğin [1, 1, 5] için 115, 151, 115, 151, 511, 511 elde edilir. Ancak bir kopya yalnızca daha önce oluşturulmuş bir düzenlemeyi tekrarlar; dolayısıyla kesin olarak büyük olan ilk düzenleme yine bir sonrakidir.

Sayı n! oranında büyür: 12 farklı değerin 479,001,600 düzenlemesi vardır.

Algoritma

nums'un bir kopyasını sıralayıp pool içine yerleştir.
pool içindeki kullanılmamış öğeleri soldan sağa seçerek derinlik öncelikli düzenlemeler oluştur.
Bir düzenleme tamamlandığında, bunu nums ile konum konum karşılaştır.
nums'dan büyük olan ilk düzenlemeyi döndür.
Hiçbiri daha büyük değilse pool'u döndür.

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

Dönüm noktasını bul, yer değiştir, son eki tersine çevir

Sezgi

Pivot, sağındaki komşusundan küçük olan sağdan ilk değerdir: [2, 5, 4, 1] dizisindeki 2. Büyüyebilen en sağdaki konumdur ve mümkün olan en sağdaki konumu büyütmek artışı en küçük tutar.

Pivotu, sonek içindeki ondan kesin olarak büyük olan en küçük değerle değiştirin. Sonek azalan sıradadır; bu nedenle pivotdan büyük olan en sağdaki değer 4'tür ve sonuç [4, 5, 2, 1] olur. Eski pivot, 4'ün bulunduğu yere sığdığı için sonek hâlâ azalan sıradadır. Baştaki değer artık daha büyük olduğuna göre sonek mümkün olduğunca küçük, yani artan sırada olmalıdır; azalan bir diziyi tersine çevirmek bunu sağlar: [4, 1, 2, 5].

Pivot yoksa dizi en büyük sıralamadır; dizinin tamamını tersine çevirmek en küçüğünü verir. Her adım bir tarama veya bir tersine çevirmedir: O(n) zaman ve O(1) bellek; ancak R sürümü O(n) boyutunda bir kopya döndürür.

Algoritma

i değerini n-2 olarak ayarlayın ve nums[i] ≥ nums[i + 1] olduğu sürece sola doğru ilerletin.
i ≥ 0 ise j değerini n-1 olarak ayarlayın ve nums[j] ≤ nums[i] olduğu sürece sola doğru ilerletin, ardından nums[i] ile nums[j] değerlerini yer değiştirin.
i + 1 konumundan sona kadar olan kısmı, birbirlerine doğru ilerleyen iki indeksle tersine çevirin.
nums değerini döndürün.

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

Tuzaklar ve uç durumlar

Pivot aramasında > yerine ≥ kullanmak. [3, 2, 2, 1] dizisinde 2, 2 çifti bir yükseliş değildir ve burada durmak, büyütülemeyen bir pivot seçilmesine neden olur.
Pivotla eşit bir değerle yer değiştirmek. [1, 5, 1] dizisinde iki 1'in yerini değiştirmek hiçbir şeyi değiştirmez; kesinlikle daha büyük bir değer ara.
Sonek içindeki en büyük değerle yer değiştirmek. [2, 5, 4, 1] dizisinde bu, 5'i başa getirir ve 4 ile başlayan tüm düzenlemeleri atlar.
Pivot bulunamaması durumunu atlamak. En büyük düzenleme, tüm dizi ters çevrilerek sıralı biçimde geri dönmelidir.
Rust'ta n-2 ile başlayan bir usize indeksi, n = 1 olduğunda panik oluşturur; pivot olmadığında 0'ın ötesine geçmek de panik oluşturur. İşaretli bir indeks kullan veya 1'den geriye doğru say.

Sıkça sorulan sorular3

Next Permutation'ın zaman karmaşıklığı nedir?

O(n). Sağdan yapılan bir tarama pivotu bulur, ikinci tarama takas edilecek değeri bulur ve tek bir ters çevirme soneki düzeltir. Her şey dizinin içinde gerçekleştiğinden ek bellek O(1)'dir.

Soneki sıralamak yerine neden tersine çeviriyorsun?

Takastan sonra sonek hâlâ azalan sırada olduğundan, onu ters çevirmek artan sırada sıralamak için yeterlidir. Ters çevirme işlemi O(n) sürer; sıralama ise aynı sonucu O(n log n) sürede verir.

Sonraki Permütasyon yinelenen değerlerle çalışır mı?

Evet, her iki karşılaştırma da eşit değerleri daha büyük kabul etmediği sürece. Pivot araması eşit komşuları ≥ ile, takas araması ise pivota eşit değerleri ≤ ile atlar. Sonra [1, 5, 1], bir sonraki farklı diziliş olan [5, 1, 1] hâline gelir.

def nextPermutation(nums):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argüman

nums = [2, 5, 4, 1]

Beklenen Çıktı

[4, 1, 2, 5]