Leetcode 136 Single Number

Follow up: Could you implement a solution with a linear runtime complexity and without using extra memory?

• Bir seen adında liste oluştururuz.Bize verilen listede dolaşarak gördüğümüz elemanları eğer seen listesinde yok iseler seen listesine ekleriz.Eğer seen listesinde var iseler o zaman bu elemanı seen listesinden sileriz.Verilen listeyi taramamız bittiğinde seen listesindeki eleman tek olan elemandır.

• Listeyi set olacak şekilde düzenleriz.
• Sadece benzersiz olanları içeren set listenin toplamınını 2 ile çarparız.
• Elimizdeki ilk listenin toplamını alırız.
• Set listenin 2 katından elimizdeki listeyi çıkardığımızda tekrar etmeyen sayı kalacaktır.

• Elimizdeki listeyi XOR layarak tek olan elemana ulaşabiliriz.XOR yöntemi sayesinde çiftler birbirlerini sıfırlayacaklardır.

    def singleNumber(self, nums):
        seen = []
        for num in nums:
            if num not in seen:
                seen.append(num)
            else:
                seen.remove(num)
        return seen[-1]

    def singleNumber(self, nums: List[int]) -> int:
        return 2*sum(set(nums))-sum(nums)

def singleNumber(nums):
    a = 0
    for i in nums:
        a ^= i
    return a