Single Number
Her değerin tam olarak iki kez göründüğü, yalnızca bir değerin ise bir kez göründüğü bir nums listesi verilir. Bir kez görünen değeri döndür.
Fonksiyon
- numsinteger-array
- Bir değer dışında her değerin iki kez göründüğü bir liste
- Döndürürinteger
- yalnızca bir kez görünen değer
Kısıtlar
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Bir değer dışında her değer tam olarak iki kez görünür; bu değer ise yalnızca bir kez görünür.
Örnekler
- Girdi
- nums = [8, 3, 8]
- Çıktı
- 3
- Açıklama
- 8 iki kez, 3 ise bir kez göründüğünden yanıt 3'tür.
- Girdi
- nums = [5, -2, 7, 5, 7]
- Çıktı
- -2
- Açıklama
- 5 ve 7 ikişer kez görünür, -2 ise yalnızca bir kez görülen değerdir. Negatif bir yanıt, pozitif bir yanıtla aynı şekilde bulunur.
- Girdi
- nums = [42]
- Çıktı
- 42
- Açıklama
- Tek bir değeri olan bir listenin hiç çifti yoktur; bu nedenle yanıt o değerdir.
Gönderirken +13 gizli test
Ek soru
Ya her değer bir kez dışında üç kez görünseydi ne olurdu? XOR tek başına artık üçlüleri birbirini götürecek şekilde kullanılamaz. Yine de tek değeri O(n) sürede ve O(1) ek bellek kullanarak bulabilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Her eşit değer çifti yok edilebilseydi, geriye yalnızca cevap kalırdı. İki eşit sayıyı hiçbir şeye dönüştüren bir işlem var mı?
XOR şunu yapar:
x ^ x0olur vex ^ 0xolur. Ayrıca sıralama önemli değildir; bu nedenle bir değerin iki kopyasının birbirini götürmesi için yan yana durmaları gerekmez.0değerinden başlayan bir değişken tut.numsiçindeki her değeri bu değişkene XOR işlemiyle uygula, ardından değişkeni döndür. Map kullanmaya ve sıralama yapmaya gerek yok.
Çözüm
Eşi olmayan tek değeri bulmak bir sayma problemidir ve bir hash map tek geçişte her değeri sayar. Sorun bellektir: map, listeyle birlikte büyür. XOR, sayma gereksinimini tamamen ortadan kaldırır; çünkü bir değeri kendisiyle XOR’lamak 0 verir. Listenin tamamındaki değerleri birbirleriyle XOR’layın; her çift kendini yok eder ve tek geçişte, tek bir değişkenle geriye tek değer kalır.
Her değeri tarayarak sayın
Doğru, ama en büyük testlerde bitmiyor
Sezgi
Sırayla her değeri ele al ve kaç kez geçtiğini saymak için listenin tamamını tara. Bir çiftteki değer 2 sayılır. Tek değer 1 sayılır; bu yüzden sayısı 1 olan ilk değeri döndür.
Bu doğrudur; çünkü sayımlar doğrudan yanıtın tanımından çıkar ve bir sayaç dışında ek bellek gerektirmez.
Yavaştır; çünkü n değerin her biri, n değerin tamamının taranmasına neden olur. Tek değer 9,999 elemanlı bir listenin sonunda yer alıyorsa bu, yaklaşık 10^8 karşılaştırma demektir.
Algoritma
numsiçindeki her değer üzerinde döngü kur.- Tüm listeyi tara ve ona eşit olan değerleri say.
- Sayı 1 ise o değeri döndür.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Bir hash map ile sayım yapın
Sezgi
Listedeki her değeri yeniden taramak, aynı işi tekrarlar. Bunun yerine tüm değerleri tek geçişte say: değerden sayıya eşleme yapan bir hash map kullan; her adımda mevcut değerin sayısını 1 artır.
[5, -2, 7, 5, 7] için eşleme sonunda 5 → 2, -2 → 1, 7 → 2 olur. Eşleme üzerinde yapılan ikinci bir geçiş, sayısı 1 olan girdiyi bulur; bu değer -2'dir.
Her değer bir eşleme güncellemesi gerektirir, bu nedenle zaman karmaşıklığı O(n)'dir. Eşleme yaklaşık n/2 girdi tutar; bu da O(n) ek bellek demektir. Yerleşik bir eşlemesi olmayan C'de, değerler küçük olduğundan value + 10^4 ile indekslenen bir sayaç dizisi aynı işlevi görür.
Algoritma
- Değerden sayıya boş bir eşleme oluşturun.
numsiçindeki her değer için sayısına 1 ekleyin.- Eşlemenin üzerinden geçin ve sayısı 1 olan değeri döndürün.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0Tüm değerleri XOR'la
Sezgi
XOR iki sayıyı bit bit karşılaştırır ve farklı oldukları bit konumlarında biti 1 yapar. Bundan üç sonuç çıkar: x ^ x = 0, x ^ 0 = x ve işlemlerin sırası önemli değildir.
Bu nedenle listenin tamamına, başlangıçta 0 olan tek bir değişkenle XOR uygulayın. İşlemleri her çift kendi eşiyle eşleşecek şekilde yeniden gruplayabilirsiniz; böylece her çift 0 olur. Geriye 0 ^ single kalır ve bu da tek kalan değerdir. [8, 3, 8] için: 0 ^ 8 = 8, sonra 8 ^ 3 = 11, ardından 11 ^ 8 = 3.
Negatif sayılar da işe yarar. XOR, iki'nin tümleyeni gösterimindeki bitler üzerinde işlem yapar ve birbirine eşit iki negatif sayının bitleri de eşittir; bu nedenle diğer tüm çiftler gibi birbirlerini götürürler. Döngü her değeri bir kez okur ve tek bir değişken tutar: O(n) zaman ve O(1) ek bellek.
Algoritma
resultdeğerini 0 olarak ayarla.numsiçindeki her değer içinresultdeğeriniresult ^ valueolarak ayarla.resultdeğerini döndür.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Tuzaklar ve uç durumlar
XOR döngüsü kısadır, bu yüzden hatalar döngünün nerede başladığında ve insanların başvurduğu alternatiflerde gizlidir.
resultdeğerininums[0]olarak başlatıp ardından 0. indeks de dahil olmak üzere tüm değerler üzerinde döngü yapmak. İlk değer XOR işlemine iki kez katılır ve kendini iptal eder. 0'dan başla ya da 0. indeksi atla.- Komşuları ikişer adımla sıralayıp karşılaştırmak, sonra tek değerin son eleman olabileceğini unutmak.
[1, 1, 2]içinde eşleşmeyen bir çift yoktur ve yanıt geriye kalan 2'dir. 2 × sum(distinct values) - sum(nums)kullanmak. Doğru sayıyı verir ama farklı değerler kümesiO(n)bellek gerektirir; XOR sürümü bundan kaçınır.- XOR'un başka sayıda tekrar için de işe yaramasını beklemek. XOR, çift sayıda görünen değerleri iptal eder. Bir değer üç kez görünseydi, bir kopyası kalır ve yanıtı bozardı.
Sıkça sorulan sorular4
Single Number algoritmasının zaman karmaşıklığı nedir?
XOR çözümü, her değeri bir kez okuduğu ve tek bir değişken tuttuğu için O(n) zamanda çalışır ve O(1) ek alan kullanır. Bir hash map de O(n) zaman alır ancak O(n) bellek gerektirir. Her değeri yeni bir taramayla saymak O(n²) zaman alır.
XOR, Single Number problemini neden çözer?
Bir sayıyı kendisiyle XOR işlemine tabi tutmak 0 verir, 0 ile XOR işlemi hiçbir şeyi değiştirmez ve işlemlerin sırası önemli değildir. Bu nedenle, listenin tamamına XOR işlemi uyguladığında her çift bir araya getirilip 0'a sadeleşir. Yalnızca eşi olmayan değer kalır.
XOR numarası negatif sayılarla çalışır mı?
Evet. XOR, sayıyı saklayan bitler üzerinde çalışır ve negatif sayılar ikinin tümleyeni biçiminde saklanır. Birbirine eşit iki negatif sayının bitleri aynıdır, bu yüzden pozitif sayılarda olduğu gibi birbirini tam olarak yok ederler. [5, -2, 7, 5, 7] içinde sonuç -2'dir.
Diğer değerler üç kez göründüğünde bunu nasıl çözersin?
XOR çiftleri iptal eder, üçlüleri değil; bu yüzden burada başarısız olur. Bunun yerine, 32 bitin her birinde kaç değerin bu biti ayarlanmış olarak içerdiğini sayın. Her bit için bu sayının 3'e bölümünden kalan, tek değerin o biti olur; çünkü üçlüler 3'ün katlarını ekler. Bu işlem yine O(n) zamanda ve O(1) ek bellekle çalışır.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def singleNumber(nums):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
nums = [8, 3, 8]
Beklenen
3