Rotate Array

Q: Apa yang terjadi ketika k lebih besar daripada panjang array?

Setiap n langkah membuat array kembali ke urutan awalnya, jadi hanya k mod n langkah yang penting. Memutar [10, 20, 30] sebanyak 7 langkah sama dengan memutarnya sebanyak 1 langkah, sehingga hasilnya [30, 10, 20] . Jika k merupakan kelipatan n , array tidak berubah.

Q: Bagaimana cara memutar array ke kiri?

Rotasi ke kiri sebanyak k sama dengan rotasi ke kanan sebanyak n - (k mod n) . Dengan pembalikan, balik k mod n nilai pertama, lalu sisanya, kemudian seluruh array. Keduanya tetap memiliki kompleksitas waktu O(n).

SedangArray dan string Two pointers

+10

Kamu mendapatkan array bilangan bulat nums dan sebuah angka k. Putar array ke kanan sebanyak k langkah: dalam satu langkah, setiap nilai berpindah satu posisi ke kanan, dan nilai terakhir berpindah kembali ke posisi pertama. Kembalikan array yang sudah diputar.

k bisa jauh lebih besar daripada panjang array.

Fungsi

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

numsinteger-array: array bilangan bulat yang akan dirotasi
kinteger: berapa banyak langkah untuk berputar ke kanan
Mengembalikaninteger-array: nums diputar ke kanan sebanyak k langkah

Batasan

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

Contoh

Input: nums = [4, 9, 1, 6, 3]k = 2
Output: [6, 3, 4, 9, 1]
Penjelasan: Dua langkah ke kanan membawa dua nilai terakhir, 6 dan 3, ke bagian depan. Tiga nilai lainnya bergeser dua tempat ke kanan dan tetap dalam urutan yang sama: [6, 3, 4, 9, 1].

Pertanyaan lanjutan

Bisakah kamu memutar di tempat dengan memindahkan setiap nilai langsung ke (i + k) mod n dan meneruskan nilai yang tergeser? Ada berapa siklus yang terbentuk?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

Setiap n langkah mengembalikan array ke posisi awalnya, jadi pertama-tama kurangi k, yang bisa bernilai 10^9, menjadi k mod n. Lalu, tulis setiap nilai langsung ke indeks akhirnya di array kedua, atau dapatkan hasil yang sama di dalam array dengan tiga pembalikan dan memori tambahan O(1).

Salin setiap nilai ke indeks barunya

Intuisi

Setelah k langkah, nilai pada indeks i berada di (i + k) mod n, jadi tulis nilai itu langsung di sana tanpa melakukan langkah-langkahnya. Kurangi k menjadi k mod n terlebih dahulu: rotasi sebanyak n mengembalikan setiap nilai ke posisi semula, jadi dengan k = 7 dan n = 3, hanya tersisa satu langkah.

Satu kali lintasan menempatkan semua n nilai: waktu O(n), ditambah memori O(n) untuk hasilnya. Kamu tidak bisa menulis langsung ke dalam nums dengan cara ini, karena setiap penulisan akan menimpa nilai yang belum kamu pindahkan.

Algoritma

Atur n menjadi panjang nums dan ganti k dengan k mod n.
Buat array hasil dengan panjang n.
Untuk setiap indeks i, simpan nums[i] di result[(i + k) mod n].
Kembalikan hasilnya.

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

Tiga pembalikan di tempat

Intuisi

Pisahkan array menjadi A, yaitu n-k nilai pertama, dan B, yaitu k nilai terakhir. Array yang dirotasi adalah B diikuti A, dengan urutan setiap blok tetap seperti semula. Membalik seluruh array membalik urutan blok dan urutan elemen di dalam setiap blok, jadi B berada di awal tetapi terbaca terbalik, begitu juga A. Membalik setiap blok sekali lagi akan memulihkan urutan elemennya.

Untuk [4, 9, 1, 6, 3] dan k = 2: membalik semuanya menghasilkan [3, 6, 1, 9, 4], membalik dua elemen pertama menghasilkan [6, 3, 1, 9, 4], dan membalik tiga elemen terakhir menghasilkan [6, 3, 4, 9, 1].

Setiap nilai ditukar paling banyak dua kali, jadi waktunya O(n) dan memori tambahannya hanya beberapa variabel indeks (O(n) di R, yang menyalin vector ketika helper pembalik mengubahnya).

Algoritma

Atur n menjadi panjang nums dan ganti k dengan k mod n.
Balik seluruh array, dari indeks 0 hingga n-1.
Balik blok pertama, dari indeks 0 hingga k-1.
Balik blok kedua, dari indeks k hingga n-1.
Kembalikan nums.

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

Jebakan dan kasus tepi

Lupa menghitung k mod n. Dengan k = 10^9, rotasi selangkah demi selangkah tidak akan pernah selesai, dan membalik k nilai pertama akan membaca jauh melewati akhir array.
Melakukan slicing tanpa modulo. Di Python, nums[-k:] + nums[:-k] dengan k = 7 dan n = 3 mengembalikan array tanpa perubahan, karena kedua slice berhenti di tepi array.
Membalik dalam urutan yang salah. Membalik kedua blok terlebih dahulu, lalu seluruh array, menghasilkan rotasi ke kiri.
Kesalahan satu indeks di tepi blok: blok pertama berakhir di indeks k-1 dan blok kedua dimulai di k. Di Lua dan R, yang menghitung mulai dari 1, bloknya adalah 1..k dan k+1..n.

Pertanyaan yang sering diajukan3

Apa kompleksitas waktu dari Rotate Array?

O(n) untuk pendekatan penyalinan maupun tiga pembalikan, karena setiap nilai dipindahkan sejumlah kali yang konstan. Mengurangi k dengan k mod n terlebih dahulu mencegah k yang sangat besar berpengaruh. Memutar satu langkah setiap kali membutuhkan O(n × k).

Apa yang terjadi ketika k lebih besar daripada panjang array?

Setiap n langkah membuat array kembali ke urutan awalnya, jadi hanya k mod n langkah yang penting. Memutar [10, 20, 30] sebanyak 7 langkah sama dengan memutarnya sebanyak 1 langkah, sehingga hasilnya [30, 10, 20]. Jika k merupakan kelipatan n, array tidak berubah.

Bagaimana cara memutar array ke kiri?

Rotasi ke kiri sebanyak k sama dengan rotasi ke kanan sebanyak n - (k mod n). Dengan pembalikan, balik k mod n nilai pertama, lalu sisanya, kemudian seluruh array. Keduanya tetap memiliki kompleksitas waktu O(n).

def rotate(nums, k):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

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

Output yang diharapkan

[6, 3, 4, 9, 1]