First Missing Positive

+10

Kamu mendapatkan array bilangan bulat nums yang tidak terurut. Kembalikan bilangan bulat positif terkecil (1 atau lebih besar) yang tidak muncul di nums. Array tersebut dapat berisi bilangan negatif, nol, nilai berulang, dan nilai yang jauh lebih besar daripada panjangnya.

Fungsi

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: bilangan bulat yang belum diurutkan, yang mungkin berulang dan bisa negatif, nol, atau sangat besar
Mengembalikaninteger: bilangan bulat positif terkecil yang tidak ada di nums

Batasan

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Nilai-nilai ini tidak disusun dalam urutan tertentu dan dapat berulang.

Contoh

Input: nums = [5, -2, 1, 3, 2, 9]
Output: 4
Penjelasan: 1, 2, dan 3 semuanya ada di array, sedangkan 4 tidak ada, jadi jawabannya adalah 4. Angka 5 dan 9 tidak penting jika ada nilai yang lebih kecil yang hilang.

Pertanyaan lanjutan

Bisakah kamu menemukan jawabannya dalam waktu O(n) dengan hanya menggunakan memori tambahan O(1)?

Petunjuk

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

0 dari 3 dibuka

Solusi

Pengurutan membutuhkan waktu O(n log n) dan hash set membutuhkan memori tambahan O(n). Ada batas yang lebih baik dari keduanya: n nilai mencakup paling banyak n angka dari 1 hingga n+1, jadi jawabannya paling banyak n+1. Hanya nilai dari 1 hingga n yang penting, dan array memiliki n slot untuk mencatatnya, sehingga memori tambahan turun menjadi O(1).

Uji setiap kandidat dengan pemindaian menyeluruh

Benar, tetapi tidak selesai pada tes terbesar

Intuisi

Uji kandidat 1, 2, 3, ... secara berurutan. Untuk setiap kandidat, telusuri seluruh array, lalu kembalikan kandidat pertama yang tidak ditemukan dalam penelusuran. Berdasarkan batas tersebut, kamu tidak pernah menguji angka yang lebih besar dari n+1.

Ketika array berisi angka 1 sampai n, rata-rata setiap kandidat ditemukan setelah penelusuran separuh array, sehingga n = 10^4 membutuhkan sekitar n²/2 = 5 × 10^7 perbandingan.

Algoritma

Atur candidate ke 1.
Pindai nums untuk mencari elemen yang sama dengan candidate, lalu berhenti pada elemen pertama.
Jika tidak ada elemen yang cocok, kembalikan candidate.
Jika ada, tambahkan 1 ke candidate dan pindai lagi. Kamu tidak akan melewati n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # n values cannot cover all of 1..n+1, so one of these candidates is missing
    for candidate in range(1, n + 2):
        found = False
        for num in nums:
            if num == candidate:
                found = True
                break
        if not found:
            return candidate

Tandai nilai 1 hingga n dalam array flag

Intuisi

Karena jawabannya paling besar n+1, abaikan nilai yang kurang dari 1 atau lebih dari n. Array boolean present dengan panjang n+1 mencatat nilai lainnya, sehingga nilai seperti 10^9 tidak pernah disimpan. Kembalikan v pertama dari 1 sampai n yang flagnya bernilai false, atau n+1 jika semua flag sudah disetel.

Pada contoh pertama, n = 6: flag untuk 1, 2, 3, dan 5 disetel, -2 dan 9 dilewati, dan flag pertama yang belum disetel adalah 4. Dua lintasan linear membutuhkan waktu O(n), dan flag membutuhkan memori O(n).

Algoritma

Buat present, n+1 penanda yang disetel ke false.
Untuk setiap nilai v di nums dengan 1 ≤ v ≤ n, setel present[v] ke true.
Kembalikan v pertama dari 1 hingga n yang penandanya false.
Jika tidak ada, kembalikan n+1.

def firstMissingPositive(nums):
    n = len(nums)
    # present[v] says whether v is in nums; only 1..n can matter
    present = [False] * (n + 1)
    for num in nums:
        if 1 <= num <= n:
            present[num] = True
    for v in range(1, n + 1):
        if not present[v]:
            return v
    return n + 1

Letakkan setiap nilai di slotnya sendiri

Intuisi

Nilai v berada pada indeks v-1. Jika setiap nilai dari 1 hingga n berada di tempatnya, indeks pertama i yang tidak berisi i+1 menunjukkan jawabannya.

Pada setiap indeks, tukar nilainya ke tempatnya selama nilainya berada di antara 1 dan n dan tempatnya belum berisi nilai tersebut. Nilai yang kembali mungkin juga perlu dipindahkan. Memeriksa tempatnya, bukan i, mencegah duplikat: dalam [1, 1], angka 1 kedua melihat angka 1 di indeks 0 dan tetap di sana.

Dalam contoh pertama, indeks 0 mengirim angka 5 ke tempatnya, lalu angka 2 yang kembali. Setelah itu, angka 1 dan 3 masuk ke tempatnya, sehingga tersisa [1, 2, 3, -2, 5, 9]: indeks 3 adalah slot pertama yang salah, jadi jawabannya 4.

Setiap pertukaran menempatkan satu nilai di tempatnya secara permanen, jadi perulangan bagian dalam melakukan paling banyak n pertukaran secara total: waktu O(n), dan memori O(1), kecuali di R, yang menyalin vector yang diubahnya.

Algoritma

Untuk setiap indeks i dari 0 hingga n-1:
Selama 1 ≤ nums[i] ≤ n dan nums[nums[i]-1] ≠ nums[i], tukar nums[i] dengan nums[nums[i]-1].
Setelah tahap penempatan, cari indeks pertama i yang memenuhi nums[i] ≠ i+1, lalu kembalikan i+1.
Jika setiap slot menyimpan nilainya sendiri, kembalikan n+1.

def firstMissingPositive(nums):
    n = len(nums)
    for i in range(n):
        # Keep swapping until slot i holds a value that has no slot or is already home
        while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
            home = nums[i] - 1
            nums[i], nums[home] = nums[home], nums[i]
    # The first slot that does not hold its own value names the answer
    for i in range(n):
        if nums[i] != i + 1:
            return i + 1
    return n + 1

Jebakan dan kasus tepi

Menghentikan pertukaran saat nums[i] == i+1, bukan saat posisi seharusnya sudah berisi nilainya. Dengan [1, 1], kedua angka 1 akan terus bertukar.
Menggunakan if alih-alih while untuk menukar. Pada contoh pertama, angka 2 yang kembali dari indeks 4 tidak pernah mencapai indeks 1, sehingga kamu mengembalikan 2, bukan 4.
Menulis nums[i] = nums[nums[i]-1] lalu mengindeks lagi dengan nums[i], sehingga yang terbaca adalah indeks posisi seharusnya setelah nilainya berubah. Simpan indeks posisi seharusnya terlebih dahulu.
Melewatkan pemeriksaan rentang, sehingga 0, -2, atau 10^9 mengarah ke indeks di luar array.
Mengembalikan n saat semua posisi sudah benar. Untuk [4, 2, 1, 3], jawabannya adalah 5.

Pertanyaan yang sering diajukan3

Berapa kompleksitas waktu First Missing Positive?

Solusi penempatan berjalan dalam waktu O(n) dengan ruang ekstra O(1). while loop berada di dalam for loop, tetapi setiap pertukaran menempatkan sebuah nilai di indeks akhirnya, sehingga keseluruhan proses melakukan paling banyak n pertukaran. Versi dengan array flag membutuhkan waktu O(n) dan memori O(n), sedangkan pemindaian untuk setiap kandidat membutuhkan waktu O(n²).

Mengapa jawabannya tidak pernah lebih besar dari n+1?

Angka 1 hingga n+1 adalah n+1 nilai yang berbeda, dan array dengan panjang n menampung paling banyak n nilai yang berbeda, jadi salah satunya hilang. Jawabannya adalah n+1 tepat ketika array tersebut memuat semua nilai dari 1 hingga n.

Apakah solusi in-place mengubah array input?

Ya, cara itu mengatur ulang nilai. Jika pemanggil membutuhkan urutan asli, salin array terlebih dahulu, sehingga penggunaan memori tambahan kembali menjadi O(n). Method lain yang bekerja di tempat mengganti setiap nilai di luar rentang 1 hingga n dengan n+1, lalu menandai v sebagai nilai yang ada dengan membuat nums[v-1] negatif; cara itu juga mengubah array.

def firstMissingPositive(nums):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

nums = [5, -2, 1, 3, 2, 9]

Output yang diharapkan

First Missing Positive

Fungsi

Batasan

Contoh

Petunjuk

Solusi

Uji setiap kandidat dengan pemindaian menyeluruh

Tandai nilai 1 hingga n dalam array flag

Letakkan setiap nilai di slotnya sendiri

Jebakan dan kasus tepi

Pertanyaan yang sering diajukan3

Soal serupa