LeetCode 136. Single Number(只出现一次的数)
题目描述
Given an 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?
解法一
思路
这题是用异或求解的经典题目了。首先需要明白异或(^)的几个性质:
- 顺序无关:多个元素异或的结果与元素的顺序无关。
- 同一个数异或两次等于没有异或:如
4 ^ 3 ^ 4 = 3
。 - 一个数与0异或的结果为其本身:如
3 ^ 0 = 3
。
明白这些性质了这题就非常容易了,result
初始值为0,将数组中每个元素都与result
作异或并更新result
,最终result
的值就是那个唯一只出现一次的元素了。
Python
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
result = 0
for num in nums:
result ^= num
return result
Java
public class Solution {
public int singleNumber(int[] nums) {
int result = 0;
for (int num : nums) {
result ^= num;
}
return result;
}
}
C++
class Solution {
public:
int singleNumber(vector<int> &nums) {
int result = 0;
for (auto num:nums) {
result ^= num;
}
return result;
}
};