Rotate Array

Q: k, dizinin uzunluğundan büyük olduğunda ne olur?

Her n adımda dizi başlangıç sırasına geri döner; bu nedenle yalnızca k mod n adımı önemlidir. [10, 20, 30] dizisini 7 adım döndürmek, 1 adım döndürmekle aynıdır ve sonuç [30, 10, 20] olur. k , n 'nin katı olduğunda dizi değişmez.

Q: Diziyi sola nasıl döndürürsünüz?

k kadar sola döndürme, n - (k mod n) kadar sağa döndürmedir. Ters çevirmelerle, önce ilk k mod n değeri, sonra geri kalanını, ardından dizinin tamamını ters çevir. Her iki işlem de O(n) zaman alır.

OrtaDiziler ve dizgiler İki işaretçi

+10

Bir tam sayı dizisi nums ve k sayısı verilir. Diziyi k adım sağa döndür: Bir adımda her değer bir konum sağa kayar ve son değer başa geçer. Döndürülmüş diziyi döndür.

k, dizinin uzunluğundan çok daha büyük olabilir.

Fonksiyon

rotate(nums: integer-array, k: integer) → integer-array

numsinteger-array: döndürülecek tamsayı dizisi
kinteger: sağa döndürmek için kaç adım
Döndürürinteger-array: nums k adım sağa döndürülmüş

Kısıtlar

1 ≤ nums.length ≤ 5000
-10⁴ ≤ nums[i] ≤ 10⁴
0 ≤ k ≤ 10⁹

Örnekler

Girdi: nums = [4, 9, 1, 6, 3]k = 2
Çıktı: [6, 3, 4, 9, 1]
Açıklama: Sağa doğru iki adım, son iki değer olan 6 ve 3'ü başa taşır. Diğer üç değer iki sıra sağa kayar ve sıralarını korur: [6, 3, 4, 9, 1].

Ek soru

Her değeri doğrudan (i + k) mod n konumuna taşıyıp yerinden ettiği değeri de beraberinde taşıyarak diziyi yerinde döndürebilir misin? Bu kaç çevrim oluşturur?

İpuçları

Tek tek açın. Her biri biraz daha fazlasını gösterir.

3 ipucundan 0 açıldı

Çözüm

Her n adımda dizi başlangıçtaki hâline döner; bu nedenle önce 10^9 olabilen k değerini k mod n değerine indirin. Ardından her değeri ikinci bir dizide doğrudan son indeksine yazın veya üç ters çevirme ve O(1) ek bellek kullanarak aynı sonucu dizinin içinde elde edin.

Her değeri yeni indeksine kopyala

Sezgi

k adım sonra, i indeksindeki değer (i + k) mod n konumunda bulunur; bu nedenle adımları uygulamadan doğrudan oraya yazın. Önce k değerini k mod n olarak küçültün: n kadar döndürmek her değeri başladığı yere geri getirir, bu yüzden k = 7 ve n = 3 için geriye yalnızca bir adım kalır.

Tek geçişte n değerin tümü yerleştirilir: O(n) zaman ve sonuç için O(n) bellek. Bu şekilde doğrudan nums içine yazamazsınız; çünkü her yazma, henüz taşımadığınız bir değerin üzerine yazar.

Algoritma

n'i nums'un uzunluğuna ayarla ve k'yi k mod n ile değiştir.
n uzunluğunda bir sonuç dizisi oluştur.
Her i indeksi için nums[i] değerini result[(i + k) mod n] konumuna yerleştir.
Sonucu döndür.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing
    result = [0] * n
    for i in range(n):
        result[(i + k) % n] = nums[i]
    return result

Yerinde üç ters çevirme

Sezgi

Diziyi, ilk n-k değerlerden oluşan A ve son k değerden oluşan B olarak ayırın. Döndürülmüş dizi, eski sıraları korunarak önce B, ardından A bloğundan oluşur. Dizinin tamamını ters çevirmek hem blokların sırasını hem de her bloğun içindeki sırayı değiştirir; böylece önce B gelir ama tersten okunur, A da aynı şekilde. Her bloğu yeniden ters çevirmek, içindeki sıralamayı eski hâline getirir.

[4, 9, 1, 6, 3] ve k = 2 için: her şeyi ters çevirmek [3, 6, 1, 9, 4] sonucunu verir; ilk iki değeri ters çevirmek [6, 3, 1, 9, 4] sonucunu verir ve son üç değeri ters çevirmek [6, 3, 4, 9, 1] sonucunu verir.

Her değer en fazla iki kez yer değiştirir; dolayısıyla zaman karmaşıklığı O(n), ek bellek kullanımı ise birkaç indeks değişkenidir (R'de O(n); çünkü ters çevirme yardımcısı vektörü değiştirdiğinde bir kopyasını oluşturur).

Algoritma

n'yi nums'un uzunluğuna ayarla ve k'yi k mod n ile değiştir.
0'dan n-1'e kadar olan indislerde tüm diziyi tersine çevir.
0'dan k-1'e kadar olan indislerde ilk bloğu tersine çevir.
k'dan n-1'e kadar olan indislerde ikinci bloğu tersine çevir.
nums'u döndür.

def rotate(nums, k):
    n = len(nums)
    k %= n  # a full turn of n steps changes nothing

    def reverse(left, right):
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

    reverse(0, n - 1)  # the last k values come to the front, backwards
    reverse(0, k - 1)  # put the front block back in order
    reverse(k, n - 1)  # and the back block
    return nums

Tuzaklar ve uç durumlar

k mod n değerini unutmak. k = 10^9 olduğunda, adım adım döndürme işlemi asla bitmez ve ilk k değeri ters çevirmek, dizinin sonunun çok ötesini okur.
Modülo uygulamadan dilimleme yapmak. Python'da, k = 7 ve n = 3 iken nums[-k:] + nums[:-k] diziyi değiştirmeden döndürür; çünkü her iki dilim de dizinin sınırında durur.
Ters çevirme sırasını yanlış uygulamak. Önce iki bloğu, en son tüm diziyi ters çevirmek sola döndürme işlemidir.
Blok sınırında bir eksik ya da fazla yapmak: ilk blok k-1 indeksinde biter, ikinci blok ise k indeksinde başlar. 1'den başlayan Lua ve R'de bloklar 1..k ve k+1..n şeklindedir.

Sıkça sorulan sorular3

Rotate Array'in zaman karmaşıklığı nedir?

Her iki yaklaşımda da (kopyalama ve üç ters çevirme) karmaşıklık O(n)'dir; çünkü her değer sabit sayıda taşınır. Önce k değerini k mod n ile azaltmak, çok büyük bir k değerinin sonucu etkilemesini önler. Her seferinde bir adım döndürmek ise O(n × k) maliyetlidir.

k, dizinin uzunluğundan büyük olduğunda ne olur?

Her n adımda dizi başlangıç sırasına geri döner; bu nedenle yalnızca k mod n adımı önemlidir. [10, 20, 30] dizisini 7 adım döndürmek, 1 adım döndürmekle aynıdır ve sonuç [30, 10, 20] olur. k, n'nin katı olduğunda dizi değişmez.

Diziyi sola nasıl döndürürsünüz?

k kadar sola döndürme, n - (k mod n) kadar sağa döndürmedir. Ters çevirmelerle, önce ilk k mod n değeri, sonra geri kalanını, ardından dizinin tamamını ters çevir. Her iki işlem de O(n) zaman alır.

def rotate(nums, k):
    # Kodu buraya yazın

Test #1

Test #2

Test #3

Argümanlar

nums = [4, 9, 1, 6, 3]
k = 2

Beklenen Çıktı

[6, 3, 4, 9, 1]