1. Problem
Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,3,2]
Output: 3
Example 2:
Input: nums = [0,1,0,1,0,1,99]
Output: 99
Constraints:
- 1 <= nums.length <= 3 * 104
- -2^31 <= nums[i] <= 2^31 - 1
- Each element in nums appears exactly three times except for one element which appears once.
2. Solution
I solved this problem like this.
- Using dictionary, count all numbers.
- Find dictionary value is 1 and return that key.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
dic = {}
for x in nums:
if x not in dic:
dic[x] = 0
dic[x] += 1
for key in dic:
if dic[key] == 1:
return key
return -1