C语言算法金手指摩尔投票法手撕绝大多数问题

C语言算法金手指——摩尔投票法

什么是摩尔投票法

摩尔投票法是一种用于在数组中查找最多元素的算法，其基本思想是采用抵消的方式，即将数组中的某个元素和其他元素抵消，如果最后剩下的元素个数大于数组长度的一半，则该元素即为所求。

摩尔投票法的过程

假设我们要查找一个数组 nums 中的最多元素，我们可以通过如下流程来实现：

1. 初始化数字x和计数器count，将它们都设置为0。

2. 遍历数组中的每一个元素：

   • 如果计数器count为0，将当前数字num[i]赋值给x。

   • 如果当前数字num[i]等于x，将计数器count加1。

   • 否则，将计数器count减一。

3. 最终的数字x即为所求。

摩尔投票法的示例

示例一

假设我们有以下数组：

nums = [3, 2, 3]

执行摩尔投票法的过程如下：

• 初始化数字x和计数器count，将它们都设置为0。

• 遍历数组中的每一个元素：

  • 1. 首先，计算器count为0，将数字nums[0]赋值给x。
  • 1. 接着，数字nums[1]不等于x，将计数器count减一。
  • 1. 再接着，计数器count变为-1，数字nums[2]不等于x，同样将计数器count减一。

• 最终数字x为3，即为所求。

示例二

假设我们有以下数组：

nums = [2, 2, 1, 1, 1, 2, 2]

执行摩尔投票法的过程如下：

• 初始化数字x和计数器count，将它们都设置为0。

• 遍历数组中的每一个元素：

  • 1. 首先，计算器count为0，将数字nums[0]赋值给x。
  • 1. 接着，数字nums[1]等于x，将计数器count加1。
  • 1. 再接着，数字nums[2]不等于x，将计数器count减一。
  • 1. 然后，数字nums[3]不等于x，同样将计数器count减一。
  • 1. 接下来，数字nums[4]不等于x，将计数器count减一。
  • 1. 接着，数字nums[5]等于x，将计数器count加1。
  • 1. 最后，数字nums[6]等于x，将计数器count加1。

• 最终数字x为2，即为所求。

摩尔投票法的总结

摩尔投票法是一种常用的数组查找算法，可以高效地查找数组中出现次数最多的元素。需要注意的是，该算法前提条件是要求数组中出现次数超过一半以上，否则得到的结果不一定是正确的。