其他

只出现一次的数字

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

说明：

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

示例 1:

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

示例 2:

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

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        #return sum(set(nums))*2-sum(nums)
        a = 0
        for num in nums:
            a = a ^ num
        return a

数组内所有元素异或

归零律：a ^ a = 0 恒等律：a ^ 0 = a 交换律：a ^ b = b ^ a 结合律：a ^b ^ c = a ^ (b ^ c) = (a ^ b) ^ c; 自反：a ^ b ^ a = b. d = a ^ b ^ c 可以推出 a = d ^ b ^ c. 例：x是二进制数0101，y是二进制数1011；则x^y=1110 [0,1,2,1,2] 则 0^1^2^1^2=0 故思路为该数组内所有元素异或最后的结果则为目标元素

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

假设数组是非空的，并且给定的数组总是存在多数元素。

img

上图为摩尔投票的理解图，题目的众数总是多余其他数的总量，那么我们设为：众数为x，其他数为y，摩尔投票，碰到x加1，碰到y-1，那么剩余的x的票数总是大于1的，题解为：

def moel(self, nums: List[int])-> int:
	count = 0# 计票
	temp = 0# 存储众数x
	for i in range(len(nums)):
		if count ==  0:
			temp = nums[i]
			count += 1
        elif temp == nums[i]:
        	count +=1
        else: 
        	count -= 1
    return temp