# 136. Single Number 只出现一次的数字

@TOC

[LeetCode]

• Total Accepted: 183838
• Total Submissions: 348610
• Difficulty: Easy

## # 题目描述

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

## # 解题方法

### # 异或

we use bitwise XOR to solve this problem :

first , we have to know the bitwise XOR in java 1. 0 ^ N = N2. N ^ N = 0 So..... if N is the single number

N1 ^ N1 ^ N2 ^ N2 .............. Nx ^ Nx ^ N

= (N1^N1) ^ (N2^N2) .............. (Nx^Nx) ^ N

= 0 ^ 0 ^ ..........^ 0 ^ N

= N

java代码如下。

public class Solution {
public int singleNumber(int[] nums) {
int returnNum=0;
for(int i=0; i<nums.length; i++){
returnNum ^=nums[i];
}
return returnNum;
}
}

AC:1ms

class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return reduce(lambda x, y: x ^ y, nums)

### # 字典

class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
count = collections.Counter(nums)
return count.most_common()[-1][0]

## # 日期

2017 年 1 月 7 日 2018 年 3 月 14 日 -- 霍金去世 2018 年 11 月 ９ 日 —— 睡眠可以