leetcode练习

169 多数元素

题目：给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

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

思路

• 排序 索引切片
  排序时间复杂度分析

def majorityElement(nums):
	nums.sort()  # list.sort() 直接在原列表进行排序，无返回值
	n = len(nums)
	reslut = nums[n//2]
	return result

# 时间复杂度O(nlogn)
# 空间复杂度O(n)
1
2
3
4
5
6
7
8

• 哈希 记录每一个元素出现的次数

def majorityElement(nums):
	counts = {}
	for elem in nums:
		counts[elem] = counts.get(elem, 0) + 1
		if counts[elem] > len(nums)/2:
			return elem
# 时间复杂度 空间复杂度都为O(n)
1
2
3
4
5
6
7

• 摩尔投票法： 核心理念为 票数正负抵消 。
  摩尔投票的思路是将众数看作正类，其他数作为异类，一个正类遇到一个异类会抵消。(可以看作一个大队伍中混合了两个小队，所有士兵战斗力相同，两个小的士兵拼杀。按顺序遍历整个大队伍，先上场的士兵soldier 为 winner。如果是同一队伍的，则战斗力+1，否则减一。返回战斗到最后的winner小队)

def majorityElement(nums):
	winner = None
	power = 0
	for soldier in nums:
		if power = 0:
			winner = soldier
		if soldier == winner:
			power += 1
		else:
			power -= 1
	return winner
1
2
3
4
5
6
7
8
9
10
11

此方法时间和空间复杂度分别为 O(N) 和 O(1) ，为本题的最佳解法。

1. 尝试访问或设置 None 值的属性会导致错误
   具有不返回任何内容的函数（隐式返回 None）。
   将变量显式设置为 None。
   将变量分配给调用不返回任何内容的内置函数的结果。
   具有仅在满足特定条件时才返回值的函数
   参考文章