Eksik değer
Görev tanımı
Problem
Bir liste, 0'dan n'ye kadar aralıktan alınmış n farklı değeri herhangi bir sırada tutuyor; yani bu aralıktan tam olarak bir değer eksik. Onu tek geçişte ve sabit ek alanla bul; bu, sıralamayı da görülen her şeyin bir kümesini (set) tutmayı da dışarıda bırakır.
Örnekler
Input: nums = [3, 0, 1]
Output: 2
Input: nums = [9, 6, 4, 2, 3, 5, 7, 0, 1]
Output: 8
Input: nums = [0]
Output: 1
Neden: edge case: eksik değer n'in kendisi olabilir
İpuçları
0 / 3
Listedeki her konumun bir indeksi var ve bu indeksler neredeyse değerlerin kendisiyle aynı aralığı kaplıyor.
Her indeksi orada duran değerle eşleştir. Tam aralığın yalnız bir üyesi eşsiz kalır; eşleşen bir çiftin kaybolduğu bir işleme ihtiyacın var.
Her indeksi ve her değeri birlikte XOR'la; var olmayan tek indeks olarak n'i de karışıma kat. Mevcut her değer eşleşen sayısıyla birbirini götürür, geriye kalan da hiç orada olmamış değerdir.
- Hedef zaman
- O(n)
- Hedef alan
- O(1)
Kısıtlar
- n distinct values drawn from 0 to n
- exactly one value of the range is missing
Çözüm
0'dan n-1'e kadarki indeksler artı fazladan n değeri, tam listenin kaplayacağı aralığın aynısını kaplar; bu yüzden indeksleri ve değerleri XOR ile birlikte katlamak neredeyse her şeyi çift çift götürür. Bir değer, indeks tarafının katkı yaptığı eşit sayıyla birbirini götürür; geriye yalnız kimsenin sağlamadığı sayı kalır. Listede olmayan tek indeksi, biriktiriciyi n ile başlatmak sağlar. Tek geçişte zaman O(n), alan O(1).
def missing(nums):
answer = len(nums) # n, the index the list does not have
for i, v in enumerate(nums):
answer ^= i ^ v # each matched pair cancels itself out
return answer
print(missing([3, 0, 1])) # -> 2
print(missing([9, 6, 4, 2, 3, 5, 7, 0, 1])) # -> 8
print(missing([0])) # -> 1
print(missing([1])) # -> 0Kodda değil de fikirde mi takıldın? XOR numaraları bunu anlatıyor.