分治法找到数组中出现次数超过一半的元素

本文主要是介绍分治法找到数组中出现次数超过一半的元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

分治法找到数组中出现次数超过一半的元素

输入格式：

1.数组元素个数
2.元素值

输入样例：

5
1 2 1 1 4

输出样例：

1

#include <stdio.h>
#define N 100010
int arr[N],n;
//Boyer-oore投票算法
int ie(int *arr,int n){int c = arr[0];int count = 1;//选举出可能的数字for(int i = 1;i<n;i++){if(count == 0){c = arr[i];count = 1;}else if(c == arr[i])count++;elsecount--;}//检查该数字是否多于一般int result = 0;for(int i = 0;i<n;i++){if(c == arr[i])result++;}//判断次数返回对应的值if(result>n/2)return c;elsereturn -1;
}
int main() {scanf("%d",&n);for(int i = 0;i<n;i++){scanf("%d",&arr[i]); }int c = ie(arr,n);if(c == -1)printf("未检测到\n");elseprintf("%d",c);return 0;
}

核心代码：

for(int i = 1;i<n;i++){if(count == 0){c = arr[i];count = 1;}else if(c == arr[i])count++;elsecount--;}

这段代码是 Boyer-Moore 投票算法的核心部分，用于在数组中找到一个出现次数超过一半的元素。算法的第一轮投票过程如下：

1. 初始化候选元素和计数器：

   • c 变量初始化为数组的第一个元素 arr[0]。
   • count 变量初始化为 1，表示 c 已经被计数了一次。

2. 遍历数组进行投票：

   • 从数组的第二个元素开始遍历（即索引为 1 的元素），直到数组的最后一个元素。

3. 更新候选元素和计数器：

   • 对于当前遍历到的元素 arr[i]：
     • 如果 count 为 0，这意味着我们需要选择一个新的候选元素。这时，我们将 arr[i] 设为新的 c，并将 count 设为 1，重新开始计数。
     • 如果 arr[i] 与当前的 c相同，这意味着我们为 c 增加了一票，因此 count 加 1。
     • 如果 arr[i] 与 c 不同，这意味着 c 丢失了一票，因此 count 减 1。

4. 结束条件：

   • 当遍历完整个数组后，count 将会是 0（如果数组中没有元素出现次数超过一半），或者 count 大于 0（如果存在一个 candidate 出现次数超过一半）。

这个算法的关键在于，如果数组中存在一个元素出现次数超过一半，那么在投票过程中，这个元素最终会被选为 c，并且 count 将会是正数。这是因为，每当我们遇到一个与当前 c不同的元素时，我们只是简单地减少 count，直到 count 为 0，然后选择下一个元素作为新的 c。这样，最终的 c 一定是出现次数最多的元素。

然而，这个算法只找到了一个候选元素，它还需要通过第二轮检查来确认这个候选元素是否真的出现次数超过一半。如果第二轮检查失败（即 c 的出现次数没有超过一半），算法将返回 -1，表示没有元素满足条件。

注意：这种算法只是可能选出这个数，大家可以举一组数据执行一遍，几乎选出来的都是对的。

这篇关于分治法找到数组中出现次数超过一半的元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---