Move Zeroes

Q: Berapa kompleksitas waktu Move Zeroes?

O(n) : kedua pendekatan membaca setiap elemen satu kali. Menyalin nilai bukan nol ke dalam array baru membutuhkan memori tambahan O(n) , sedangkan pertukaran dengan dua pointer bekerja di dalam array dengan memori tambahan O(1) .

Q: Apakah Pindahkan Angka Nol bisa dilakukan dengan lebih sedikit penulisan?

Ya. Alih-alih menukar, salin setiap nilai bukan nol ke nums[write] , lalu setelah pemindaian, isi setiap posisi dari write hingga akhir dengan 0. Dengan begitu, setiap posisi ditulis paling banyak satu kali. Kamu juga bisa melewati penukaran jika read sama dengan write , karena nilainya akan dikembalikan ke tempat yang sama.

MudahTwo pointers

+10

Kamu mendapatkan array bilangan bulat nums. Pindahkan setiap 0 ke akhir array dan pertahankan urutan nilai lainnya. Kembalikan array yang telah disusun ulang, dengan panjang yang sama seperti nums.

Fungsi

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

numsinteger-array: array bilangan bulat yang akan disusun ulang
Mengembalikaninteger-array: nums dengan nilai bukan nol di awal, dalam urutan aslinya, dan setiap 0 di akhir

Batasan

1 ≤ nums.length ≤ 5000
-10⁵ ≤ nums[i] ≤ 10⁵

Contoh

Input: nums = [0, 4, 0, 7, 2]
Output: [4, 7, 2, 0, 0]
Penjelasan: Nilai yang bukan 0 adalah 4, 7, dan 2, dan urutannya tetap sama di bagian depan. Dua angka 0 mengisi dua tempat terakhir.

Pertanyaan lanjutan

Bisakah kamu memindahkan setiap 0 ke depan, dengan tetap mempertahankan urutan nilai lainnya, dalam satu kali lintasan dengan memori tambahan O(1)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Kendalanya adalah menjaga nilai lainnya tetap dalam urutan semula, sehingga menukar setiap 0 dengan elemen terakhir bukanlah pilihan. Satu indeks membaca setiap elemen, indeks kedua menandai posisi nilai bukan nol berikutnya, dan satu kali lintasan menyelesaikan tugas ini di tempat.

Salin nilai yang bukan nol

Intuisi

Salin setiap nilai bukan nol ke dalam array baru sesuai urutan kamu menemukannya, lalu tambahkan nol hingga panjangnya sama dengan nums. Urutannya tetap benar karena kamu menyalin nilai sesuai urutan kamu membacanya.

Setiap elemen dibaca sekali dan ditulis sekali: waktu O(n), ditambah memori O(n) untuk array kedua.

Algoritma

Buat array hasil yang kosong.
Untuk setiap nilai dalam nums, tambahkan ke hasil jika nilainya bukan 0.
Tambahkan nol hingga hasil memiliki jumlah entri yang sama dengan nums.
Kembalikan hasil.

def moveZeroes(nums):
    result = [x for x in nums if x != 0]
    result += [0] * (len(nums) - len(result))
    return result

Dua pointer, menukar secara langsung

Intuisi

Setelah setiap langkah, berlaku dua fakta: semua yang berada sebelum write adalah nilai bukan nol yang telah terlihat sejauh ini, sesuai urutan, dan semua yang berada dari write hingga read adalah 0. Jika nums[read] bukan nol, nilainya bertukar dengan nums[write], sehingga nilai yang berada di read menjadi 0, atau tetap sama jika kedua indeks tersebut sama. Nilai bukan nol hanya melompati 0, tidak pernah saling melompati, sehingga urutannya tetap terjaga.

Pada [0, 4, 0, 7, 2], nilai 4, 7, dan 2 bertukar ke indeks 0, 1, dan 2 secara berurutan, lalu nilai 0 berakhir di indeks 3 dan 4. Satu kali lintasan tanpa array kedua: waktu O(n) dan memori O(1).

Algoritma

Atur write ke 0.
Pindahkan read dari indeks pertama ke indeks terakhir.
Jika nums[read] bukan 0, tukar nums[read] dengan nums[write], lalu tambahkan 1 ke write.
Kembalikan nums.

def moveZeroes(nums):
    write = 0  # nums[:write] holds the non-zero values found so far, in order
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

Jebakan dan kasus tepi

Menukar setiap 0 dengan elemen terakhir. Itu memindahkan angka nol, tetapi mengacak elemen lainnya: [0, 4, 7] menjadi [7, 4, 0].
Menghapus angka nol saat indeks bergerak menelusuri array. Dalam [0, 0, 5], menghapus indeks 0 menggeser angka 0 kedua ke indeks 0, sementara perulangan berlanjut ke indeks 1. Setiap penghapusan juga menggeser sisa array, sehingga perulangannya memiliki kompleksitas O(n²).
Menguji x > 0, bukan x != 0. Nilai negatif bukan angka nol: [-1, 0, -2] harus menjadi [-1, -2, 0], tetapi versi yang menyalin array akan menghasilkan [0, 0, 0].

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu Move Zeroes?

O(n): kedua pendekatan membaca setiap elemen satu kali. Menyalin nilai bukan nol ke dalam array baru membutuhkan memori tambahan O(n), sedangkan pertukaran dengan dua pointer bekerja di dalam array dengan memori tambahan O(1).

Apakah Pindahkan Angka Nol bisa dilakukan dengan lebih sedikit penulisan?

Ya. Alih-alih menukar, salin setiap nilai bukan nol ke nums[write], lalu setelah pemindaian, isi setiap posisi dari write hingga akhir dengan 0. Dengan begitu, setiap posisi ditulis paling banyak satu kali. Kamu juga bisa melewati penukaran jika read sama dengan write, karena nilainya akan dikembalikan ke tempat yang sama.

Mengapa Move Zeroes merupakan masalah dua pointer?

Satu pointer membaca setiap elemen dan pointer lainnya menandai akhir bagian depan yang sudah selesai. Keduanya hanya bergerak maju, sehingga bersama-sama melakukan satu kali lintasan. Pola baca dan tulis yang sama menghapus duplikat dari array yang sudah diurutkan atau memfilter nilai apa pun dari array secara langsung.

def moveZeroes(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [0, 4, 0, 7, 2]

Output yang diharapkan

[4, 7, 2, 0, 0]