LeetCode 136. Single Number

Problem

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

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

 

Example 1:

Input: [2,2,1]

Output: 1

 

Example 2:

Input: [4,1,2,1,2]

Output: 4

 

-Summary-

#By using bit manipulation (no extra memory)

1. for each num in the nums list, do XOR bit manipulation and return with an answer

ex) [4,1,2,1,2]

Bit manipulation: 1XOR1 = 0, 2 XOR 2=0, 0 XOR 4 = 4.  

 

 

https://www.khanacademy.org/computing/computer-science/cryptography/ciphers/a/xor-bitwise-operation

XOR bitwise operation (article) | Ciphers | Khan Academy

 

#By using extra memory of hash map

1. Create a hashtable using the python dictionary

2. for each number in the nums, we count +1 for existing keys. [if key does not exist, it will initialize the key with 0 value by defaultdict(int)]

3. create another for loop to find a key that has value 1 which is a single one. 

 

 

처음에 nums list 안에 있는 number 하나마다 count를 하여 1보다 큰건 pass하고 1인것만 return 하도록 implement 하였었는데 pass는 하였지만, 너무 오랜 시간이 걸려 Hash table을 이용하여 새로 짜 보았다. 

 

모든 문제에 대한 저작권은 LeetCode 회사에 있습니다. [Copyright © 2020 LeetCode]

https://leetcode.com/