002.多数元素

• 169.多数元素
  • 哈希表
    • 时间复杂度：O(n)
    • 空间复杂度：O(n)
  • 排序
    • 时间复杂度：O(nlogn)
    • 空间复杂度：O(1) 或 O(logn)
  • 随机化
    • 期望的时间复杂度：O(n)
    • 空间复杂度：O(1)
  • 分治
    • 时间复杂度：O(nlogn)
    • 空间复杂度：O(logn)
  • Boyer-Moore 投票算法
    • 时间复杂度：O(n)
    • 空间复杂度：O(1)

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

多数元素 - 哈希表 §

func majorityElement(nums []int) int {
	n := len(nums)
	halfN := n >> 1
	mp := make(map[int]int, n)
	for _, num := range nums {
		mp[num]++
		if mp[num] > halfN {
			return num
		}
	}
	panic("no answer")
}

多数元素 - 排序 §

func majorityElement(nums []int) int {
	sort.Ints(nums)
	return nums[len(nums) >> 1]
}

多数元素 - 随机化 §

因为超过 $\lfloor \frac{n}{2}\rfloor$ 的数组下标被众数占据了，这样我们随机挑选一个下标对应的元素并验证，有很大的概率能找到众数

func majorityElement(nums []int) int {
	n := len(nums)
	halfN := n >> 1
 
	for {
		num := nums[random(0, n)]
		if check(nums, num, halfN) {
			return num
		}
	}
}
 
// [min, max)
func random(min, max int) int {
	rand.Seed(time.Now().UnixNano())
	return rand.Intn(max - min) + min
}
 
func check(nums []int, cur, limit int) bool {
	count := 0
	for _, num := range nums {
		if num == cur {
			count++
		}
		if count > limit {
			return true
		}
	}
	return false
}

多数元素 - 分治 §

如果数 a 是数组 nums 的众数，如果我们将 nums 分成两部分，那么 a 必定是至少一部分的众数

我们可以使用反证法来证明这个结论。假设 a 既不是左半部分的众数，也不是右半部分的众数，那么 a 出现的次数少于 l / 2 + r / 2 次，其中 l 和 r 分别是左半部分和右半部分的长度。由于 l / 2 + r / 2 <= (l + r) / 2，说明 a 也不是数组 nums 的众数，因此出现了矛盾。所以这个结论是正确的。

var (
	theNums []int
)
 
func majorityElement(nums []int) int {
	theNums = nums
	return getMode(0, len(nums) - 1)
}
 
// 获取众数
func getMode(low, high int) int {
	if low == high {
		return theNums[low]
	}
 
	mid := low + (high - low) >> 1
	left := getMode(low, mid)
	right := getMode(mid + 1, high)
	if left == right {
		return left
	}
 
	leftCount := getCount(left, low, mid)
	rightCount := getCount(right, mid + 1, high)
	if leftCount > rightCount {
		return left
	}
	return right
}
 
func getCount(val, low, high int) int {
	count := 0
	for _, num := range theNums[low:high + 1] {
		if num == val {
			count++
		}
	}
	return count
}

多数元素 - Boyer-Moore 投票算法 §

思路 §

如果把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身可以看出众数比其他数多

算法 §

Boyer-Moore 算法的本质和 分治 十分类似。给出 Boyer-Moore 算法的详细步骤：

1. 维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0；
2. 遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，先将 x 的值赋予 candidate，随后我们判断 x：
   • 如果 x 与 candidate 相等，那么计数器 count 的值增加 1；
   • 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。
3. 在遍历完成后，candidate 即为整个数组的众数。

Boyer-Moore 算法的正确性较难证明

func majorityElement(nums []int) int {
	candidate := 0
	count := 0
	for _, num := range nums {
		if count == 0 {
			candidate = num
		}
		if candidate == num {
			count++
		} else {
			count--
		}
	}
	return candidate
}