# 136. Single Number

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
``````

C++ 解法一：

``````class Solution {
public:
int singleNumber(vector<int>& nums) {
unordered_set<int> st;
for (int num : nums) {
if (st.count(num)) st.erase(num);
else st.insert(num);
}
return *st.begin();
}
};
``````

Java 解法一：

``````class Solution {
public int singleNumber(int[] nums) {
Set<Integer> st = new HashSet<>();
for (int num : nums) {
}
return st.iterator().next();
}
}
``````

异或运算真值表如下：

A B
F F F
F T T
T F T
T T F

C++ 解法二：

``````class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for (auto num : nums) res ^= num;
return res;
}
};
``````

Java 解法二：

``````class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for (int num : nums) res ^= num;
return res;
}
}
``````

Single Number III

Single Number II

Missing Number

Find the Difference

Find the Duplicate Number

https://leetcode.com/problems/single-number/

https://leetcode.com/problems/single-number/discuss/42997/My-O(n)-solution-using-XOR

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation