5/10 每日一題

 Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 

Constraints:

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

使用位元運算 ,XOR

#如果我們將一個數值與自己逕行XOR運算,結果會是0,因為位元相同。

EX:1^1=0, 10^10=0, 101^101=0, 所在在list中元素重複的值相乘會得出0,最後只留下0^x=x

by the way 18^25 進行XOR運算

18的二進制=10010

25的二進制=11001  

         10010(18的二進制)

XOR 11001(25的二進制)

-----------------------------

= (1^1)(0^1)(0^0)(1^0)(0^1)>>01011=11

class Solution:

    def singleNumber(self, nums: List[int]) -> int:

        #使用XOR

        #比如[1,1,2]進行運算,會變成(1^1)^2=0^2=2

        res=0

        for i in nums:

          res=res^i

        return res

------------------------

#參考解答

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        while nums: #在nums變成空list前重複循環
            i = nums.pop(0)  #取出後確認nums是否還存在該元素,不存在就是唯一
            if i not in nums:
                return i
            ind=nums.index(i)  #當存在時就表示重複,找出另一個的索引值
            nums.pop(ind)  #再去取出,這樣重複元素就會成對消失