Bir dizide (liste) sadece bir eleman farklı sayıda tekrar ediyordur, diğer tüm elemanlar ikişer kez tekrar ediyordur. Bu tek kalan elemanı bulan bir fonksiyon yaz.
Örnek:
python
Kod:
input: [4, 1, 2, 1, 2]
output: 4- Zaman karmaşıklığı O(n) olmalı.
- Ekstra bir liste veya sözlük kullanmadan çözmeye çalış.
Bu soruyu ekstra bellek kullanmadan ve O(n) zamanda çözmenin en güzel yolu XOR operatörünü kullanmaktır.
Neden XOR?
a ^ a = 0 (aynı sayılar birbirini götürür)
a ^ 0 = a
XOR işlemi değişmeli ve birleşmelidir.
Yani bir dizideki tüm sayıları sırayla XOR'ladığımızda, çift olanlar birbirini sıfırlar ve sadece tek kalan sayı sonuç olarak elde kalır.
Python çözümü:
def single_number(nums):
result = 0
for num in nums:
result ^= num
return result
# Örnek
print(single_number([4, 1, 2, 1, 2]))