First Missing Positive

+10

Sıralanmamış bir tamsayı dizisi nums veriliyor. nums içinde bulunmayan en küçük pozitif tamsayıyı (1 veya daha büyük) döndürün. Dizi negatif sayılar, sıfırlar, tekrarlanan değerler ve uzunluğundan çok daha büyük değerler içerebilir.

Fonksiyon

firstMissingPositive(nums: integer-array) → integer

numsinteger-array: sıralanmamış tam sayılar; bunlar yinelenebilir ve negatif, sıfır ya da çok büyük olabilir
Döndürürinteger: nums içinde eksik olan en küçük pozitif tam sayı

Kısıtlar

1 ≤ nums.length ≤ 10⁴
-10⁹ ≤ nums[i] ≤ 10⁹
Değerler belirli bir sırada değildir ve tekrarlanabilir.

Örnekler

Girdi: nums = [5, -2, 1, 3, 2, 9]
Çıktı: 4
Açıklama: 1, 2 ve 3 dizide bulunuyor, 4 ise bulunmuyor; dolayısıyla cevap 4. Daha küçük bir değer eksik olduğunda 5 ve 9 önemli değildir.

Ek soru

O(n) zamanda ve yalnızca O(1) ek bellek kullanarak yanıtı bulabilir misin?

İpuçları

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

3 ipucundan 0 açıldı

Çözüm

Sıralama O(n log n) zaman alır ve bir karma küme O(n) ek bellek kullanır. Bir sınır ikisinden de iyidir: n değer, 1 ile n+1 arasındaki sayıların en fazla n tanesini kapsar; dolayısıyla yanıt en fazla n+1’dir. Yalnızca 1 ile n arasındaki değerler önemlidir ve dizide bunları kaydetmek için n yuva vardır, bu nedenle ek bellek O(1)’e düşer.

Adayların her birini tam taramayla deneyin

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

Sezgi

Adayları 1, 2, 3, ... sırasıyla test edin. Her aday için dizinin tamamını tarayın ve taramada bulunmayan ilk adayı döndürün. Sınır gereği, n+1'in ötesini asla test etmezsiniz.

Dizi 1'den n'ye kadar olan sayıları içerdiğinde, her aday ortalama olarak dizinin yarısında bulunur; bu nedenle n = 10^4 için maliyet yaklaşık n²/2 = 5 × 10^7 karşılaştırmadır.

Algoritma

candidate değerini 1 olarak ayarla.
İlk eşleşmede durarak nums içinde candidate değerine eşit bir öğe ara.
Hiçbir öğe eşleşmezse candidate değerini döndür.
Aksi takdirde candidate değerine 1 ekle ve yeniden ara. n+1 değerini asla aşmazsın.

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

Bayrak dizisinde 1'den n'ye kadar olan değerleri işaretle

Sezgi

Yanıt en fazla n+1 olduğundan, 1'in altındaki veya n'nin üzerindeki değerleri atla. n+1 uzunluğundaki bir boolean dizisi present geri kalanları kaydeder; böylece 10^9 gibi bir değer asla saklanmaz. Bayrağı false olan 1 ile n arasındaki ilk v değerini veya tüm bayraklar ayarlanmışsa n+1 değerini döndür.

İlk örnekte n = 6: 1, 2, 3 ve 5 için bayraklar ayarlanır, -2 ve 9 atlanır ve ayarlanmamış ilk bayrak 4'tür. İki doğrusal geçiş O(n) zaman alır ve bayraklar O(n) bellek kullanır.

Algoritma

present oluştur; n+1 bayrağı false olarak ayarla.
nums içindeki her v değeri için, 1 ≤ v ≤ n ise present[v] değerini true olarak ayarla.
Bayrağı false olan 1 ile n arasındaki ilk v değerini döndür.
Yoksa n+1 döndür.

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

Her değeri kendi yuvasına yerleştirin

Sezgi

Değer v, v-1 indeksinde bulunur. 1'den n'ye kadar her değer kendi yerindeyken, i+1 değerini içermeyen ilk i indeksi yanıtı verir.

Her indekste, değer 1 ile n arasındayken ve kendi yeri bu değeri zaten içermiyorken, değeri kendi yerine taşıyın. Geri gelen değerin de taşınması gerekebilir. i indeksini değil, değerin kendi yerini kontrol etmek yinelenen değerleri durdurur: [1, 1] dizisinde ikinci 1, 0 indeksinde bir 1 görür ve yerinde kalır.

İlk örnekte, 0 indeksi önce 5'i, ardından geri gelen 2'yi kendi yerine gönderir; daha sonra 1 ve 3 de kendi yerlerine gider ve geriye [1, 2, 3, -2, 5, 9] kalır: ilk yanlış yuva 3. indekstir, dolayısıyla yanıt 4'tür.

Her takas bir değeri kalıcı olarak kendi yerine koyar; bu nedenle iç döngüler toplamda en fazla n takas yapar: O(n) zaman ve R'de değiştirilen vektörün kopyalanması dışında O(1) bellek.

Algoritma

0'dan n-1'e kadar her i indeksi için:
1 ≤ nums[i] ≤ n ve nums[nums[i]-1] ≠ nums[i] olduğu sürece nums[i] ile nums[nums[i]-1] değerlerini yer değiştir.
Yerleştirme geçişinden sonra, nums[i] ≠ i+1 koşulunu sağlayan ilk i indeksini bul ve i+1 değerini döndür.
Her konum kendi değerini tutuyorsa n+1 değerini döndür.

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

Tuzaklar ve uç durumlar

Ana yuvasında değer zaten bulunduğunda değil, nums[i] == i+1 olduğunda yer değiştirmeyi durdurmak. [1, 1] ile iki 1 sonsuza kadar yer değiştirir.
while yerine if ile yer değiştirmek. İlk örnekte, 4. indexten geri gelen 2 hiçbir zaman 1. indexe ulaşmaz ve 4 yerine 2 döndürürsün.
nums[i] = nums[nums[i]-1] yazıp sonra tekrar nums[i] ile indexlemek; bu, değiştikten sonra yuva indexini okur. Önce yuva indexini kaydet.
Aralık kontrolünü atlamak; bu, 0, -2 veya 10^9 değerlerini dizinin dışındaki bir indexe gönderir.
Her yuva doğru olduğunda n döndürmek. [4, 2, 1, 3] için yanıt 5'tir.

Sıkça sorulan sorular3

İlk Eksik Pozitif'in zaman karmaşıklığı nedir?

Yerleştirme çözümü O(n) zamanda ve O(1) ek alan kullanarak çalışır. while döngüsü bir for döngüsünün içinde yer alır, ancak her takas bir değeri son indeksine yerleştirir; bu nedenle tüm çalıştırma en fazla n takas yapar. Bayrak dizisi sürümü O(n) zaman ve O(n) bellek kullanır; her aday için tarama yapmak ise O(n²) zaman alır.

Yanıt neden hiçbir zaman n+1'den büyük değildir?

1'den n+1'e kadar olan sayılar n+1 farklı değerdir ve n uzunluğundaki bir dizi en fazla n farklı değer içerir; dolayısıyla bunlardan biri eksiktir. Yanıt, dizi 1'den n'e kadar olan tüm değerleri içeriyorsa tam olarak n+1'dir.

Yerinde çözüm, girdi dizisini değiştirir mi?

Evet, değerleri yeniden düzenler. Çağıran tarafın özgün sıraya ihtiyacı varsa önce diziyi kopyalayın; bu da ek bellek kullanımını yeniden O(n) yapar. Yerinde çalışan başka bir yöntem, 1 ile n aralığının dışındaki her değeri n+1 ile değiştirir, ardından nums[v-1] değerini negatif yaparak v değerinin mevcut olduğunu işaretler; bu yöntem de diziyi değiştirir.

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

Test #1

Test #2

Test #3

Argüman

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

Beklenen Çıktı

First Missing Positive

Fonksiyon

Kısıtlar

Örnekler

İpuçları

Çözüm

Adayların her birini tam taramayla deneyin

Bayrak dizisinde 1'den n'ye kadar olan değerleri işaretle

Her değeri kendi yuvasına yerleştirin

Tuzaklar ve uç durumlar

Sıkça sorulan sorular3

Benzer problemler