DAY 24
0

# 136. Single Number

## Question

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

### Example1

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

### Example2

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

### Example3

``````Input: nums = [1]
Output: 1
``````

### Constraints

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

## 解題

### Think

• 用一個dictionary存每個數字出現的次數，最後再去看是哪一個`key`的值是`1`
• C的做法，因為後來發現我漏看題目XD，其他的數字都是出現兩次，如果用XOR的邏輯的話，相同的值回傳0，相異值回傳1，這樣最後剩下來的值，就是只出現一次的數字，其他出現兩次的都會變成0。

### Code

#### Python

``````class Solution:
def singleNumber(self, nums: List[int]) -> int:
dict = {}

for num in nums:
if num not in dict:
dict[num] = 1
else:
dict[num] += 1

for key in dict:
if dict[key] == 1:
return key
``````

#### C

``````int singleNumber(int* nums, int numsSize){
int ans = 0;

for (int index=0 ; index<numsSize ; index++) {
// printf("\nBefore: %p\n", ans);
ans ^= nums[index];
// printf("After: %p\n", ans);
}

return ans;
}
``````

### Result

• Python

• C

30天 Leetcode解題之路30