136. Single Number

  • 53.2%

https://leetcode.com/problems/single-number/?tab=Description

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?


方法一:

注意下面代码中res=0,不能是 int res,要给res赋一个初始值,否则出现错误。

1
2
3
4
5
6
7
8
9
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(auto num:nums)
res ^= num;
return res;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
for(auto num:nums)
res ^= num;
return res;
}
};

python


https://discuss.leetcode.com/topic/19563/python-different-solutions

1
2
3
4
5
6
7
def singleNumber1(self, nums):
dic = {}
for num in nums:
dic[num] = dic.get(num, 0)+1
for key, val in dic.items():
if val == 1:
return key
1
2
3
4
5
def singleNumber2(self, nums):
res = 0
for num in nums:
res ^= num
return res
1
2
def singleNumber3(self, nums):
return 2*sum(set(nums))-sum(nums)
1
2
def singleNumber4(self, nums):
return reduce(lambda x, y: x ^ y, nums)
1
2
def singleNumber(self, nums):
return reduce(operator.xor, nums)

https://discuss.leetcode.com/topic/42358/1-line-simple-python-solution

1
2
3
class Solution(object):
def singleNumber(self, nums):
return sum(list(set(nums)))*2 - sum(nums)

my code

1
2
3
4
5
6
7
8
9
10
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
res = 0
for num in nums:
res ^= num
return res


1
2
3
4
5
6
7
class Solution(object):
def singleNumber(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
return reduce((lambda x, y : x^y), nums)

java


1
2
3
4
5
6
7
8
public class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i=0; i<nums.length; i++)
res ^= nums[i];
return res;
}
}

谢谢你,可爱的朋友。