摩尔投票法

核心思想：就是在不内斗的情况下对拼消耗，剩下的就是自己人

leetcode题目：多数元素

  1. # 多数元素
  2. # 题解：通过投票法，一对一消耗，剩下的数，就是多少的元素了
  4. class Solution:
  5.     def majorityElement(self, nums: List[int]) -> int:
  6.         candidate = nums[0]    # 初始化选择第一项
  7.         count = 1    # 初始化计数为1
  9.         for i in range(1, len(nums)):
  10.             if count == 0:
  11.                 candidate = nums[i]    # 如果计数器被清零，则重置candidate
  12.             if candidate == nums[i]:
  13.                 # 如果新数字与candidate相等，则计数器加1
  14.                 count += 1
  15.             else:
  16.                 # 否则计数器减1
  17.                 count -= 1
  18.         return candidate

leetcode题目：只出现一次的数字

  1. # 排序，然后循环判断间隔两两元素是否相等，不相等则可得到结果
  3. class Solution:
  4.     def singleNumber(self, nums: List[int]) -> int:
  5.         if len(nums) == 1:
  6.             return nums[0]
  7.         nums.sort() # 对数组进行排序
  8.         for i in range(1, len(nums), 2):
  9.             # 因为排序后，相邻的两个数是相等的，所以可以两两判断，跳跃2位遍历
  10.             if nums[i-1] != nums[i]:
  11.                 return nums[i-1]
  12.             # 如果单一元素是在列表的最后，则返回
  13.             if (i+2) == len(nums):
  14.                 return nums[-1]
  1. # 依次删除列表的元素，同一个元素删除两次，报错则为目标值
  3. class Solution:
  4.     def singleNumber(self, nums: List[int]) -> int:
  5.         # 判断目标元素是否可以删除两次，报错即为目标值
  6.         while True:
  7.             d = nums[0]
  8.             nums.remove(d)
  9.             try:
  10.                 nums.remove(d)
  11.             except:
  12.                 return d
  1. # 数组求和，与去重后的和相差的就是目标值
  3. class Solution:
  4.     def singleNumber(self, nums: List[int]) -> int:
  5.         # 数组去重后求和，减去原数组求和，即为目标值
  6.         return sum(set(nums))*2 - sum(nums)
from functools import reduce
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 位运算--异或
        """
        异或：
        1、a ^ a = 0
        2、a ^ b ^ c = a ^ c ^ b
        3、a ^ c ^ a = (a ^ a) ^ c = c
        4、a ^ 0 = a
        """
        return reduce(lambda x,y: x^y, nums)