XOR numaraları
Adım 1/7
acc0bellekO(1)
8421
sıradaki4
0
1
0
0
acc0
0
0
0
0
XOR bütün listeyi tek bir değişkende biriktirir. Sıfırdan başla; ilk değer 4.
Fikir
XOR'un bütün işi gören iki özelliği var: x ^ x 0'dır, x ^ 0 da x. Üstelik sıraya da bakmaz.
O yüzden bütün listeyi baştan sona XOR'la; iki kez geçen her değer kendini siler. Geriye kalan değer tek sayıda geçmiştir — O(n) sürede ve O(1) bellekle.
Gerçek hayattan örnek
RAID 5, diğer disklerin XOR'u olan bir parity (eşlik) diski tutar. Herhangi tek bir diski kaybedersen, kalan her şeyi XOR'layarak onun içeriğini yeniden kurarsın: eksik blok, artık eşi olmayan değerdir.
Kod
Sıra sende
Boşluğu doldur.
def single_number(nums):
acc = 0
for x in nums:
acc = acc ___ x
return acc
print(single_number([9, 5, 9])) # want 5Mini quiz
1 / 3