LeetCode136. 只出现一次的数字

1 题目

给定一个 非空 整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1
1
2

示例 2：

输入: [4,1,2,1,2]
输出: 4
1
2

2 题解

2.1 Python 解法

2.1.1 方法一

由于目标元素只有一次，其他元素有两次，因此，依次删除列表的元素，同一个元素删除两次，报错则为目标值。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    	while True:
    		d = nums[0]
    		nums.remove(d)
    		try:
    			nums.remove(d)
    		except:
    			return d
1
2
3
4
5
6
7
8
9

列表.remove(元素)：移除列表中某个数据的第⼀个匹配项，不存在则报错

2.1.2 方法二

一个元素出现一次、其他出现两次，那么数组求和与去重后的和相差的就是目标值。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    	return sum(set(nums))*2-sum(nums)
1
2
3

+、* 可以用来合并、复制字符串、列表、元组

2.1.3 方法三

一个数被另一个数 异或 两次，该数本身不变

from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    	return reduce(lambda x,y:x^y,nums)
1
2
3
4

2.1.4 方法四

class Solution:
    def singleNumber(nums):
        if len(nums)==1:   #如果数组长度为1，则直接返回即可
            return nums[0]   
        nums.sort()     #对数组进行排序，使其相同元素靠在一起
        for i in range(1,len(nums),2):   #循环数组，验证前后是否相同，由于原始出现两次，因此可跳跃判断
            if nums[i-1] != nums[i]:
                return nums[i-1]
            if (i+2) == len(nums):   #判断单一元素在排序后数组的最后面
                return nums[-1]
1
2
3
4
5
6
7
8
9
10

2.1.5 方法五

注意：本方法使用了额外的空间

利用 Counter 函数

from collections import Counter
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
    	datas = Counter(nums)
    	for each in datas:
    		if datas[each]==1:
    			return each
1
2
3
4
5
6
7

关于Counter 函数的用法

from collections import Counter

l = [4, 1, 2, 1, 2]
datas = Counter(l)
print(datas) # Counter({1: 2, 2: 2, 4: 1})
1
2
3
4
5

2.2 Java 解法

2.2.1 方法一

利用异或的特性

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