大家好，我是毛毛。ヾ(´∀ ˋ)ﾉ
废话不多说开始今天的解题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

  • 

大家明天见