大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
廢話不多說開始今天的解題Day~

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

  • 

大家明天見