Problem
Leetcode problems:
- 136 sinlge number
- 137 single number II
- 260 single num III
Solution
There are two aprroches to solve these problems
- Hash table: hash table is a very important tool to solve problem related to array. dict in Python is implemented with hash table.
- Bit manipulation: not so clear about this approach, I’ll add these part latter
Hash Table
Take 137 as an example, solutions are as follows:
from typing import List
class Solution:
def singleNumber(self, nums: List[int]) -> int:
common_time = 3
special_time = 1
result_dict = {}
for n in nums:
try:
result_dict[n] += 1
if result_dict[n] == common_time:
del result_dict[n]
except:
result_dict[n] = 1
return list(result_dict.keys())[0]
Bit Manipulation
I’ll cover the approach latter.
