Given an array of numbers
nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.For example:
Given
nums = [1, 2, 1, 3, 2, 5], return [3, 5].Note:
- The order of the result is not important. So in the above example,
[5, 3]is also correct. - Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?
Thinking Process:
Looking at this you might remember
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: List[int] """ xortotal = 0 # The idea is to put the 2 unique elements in a seperate group. # By doing that, we will reudce the problem to the earlier single non-dup element among dups # and we apply xor in each gropu to get those 2 elements for elem in nums: xortotal ^= elem #Now we need to find something which is different in these 2 numbers. # Remember if any of the bits of xortotal is 1. That means those 2 number differ in that bit. # Since XOR amkes all same bits to 0. We use this different bit to seperate these 2 elem in 2 group. # Since finding rightmost elem is easy, we go for that. #Finding the rightmost set i.e. 1 bit # xor & ~(xor-1) rightmostsetbit = xortotal & ~(xortotal -1) # Now we go through all the elems in the list, and look for number which has that xth bit set and xor them, similarly # xoring those elemnts for which xth bit is not set. x,y=0,0 for elem in nums: if elem & rightmostsetbit: x ^= elem else: y ^= elem return [x,y] if __name__ == '__main__': s = Solution() print s.singleNumber([1, 2, 1, 3, 2, 5]) |
