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

2024-04-21 09:12

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

题目描述

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

输入格式:

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,表示没有元素满足条件。

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

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



http://www.chinasem.cn/article/922701

相关文章

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

hdu 1166 敌兵布阵(树状数组 or 线段树)

题意是求一个线段的和,在线段上可以进行加减的修改。 树状数组的模板题。 代码: #include <stdio.h>#include <string.h>const int maxn = 50000 + 1;int c[maxn];int n;int lowbit(int x){return x & -x;}void add(int x, int num){while

hdu 3065 AC自动机 匹配串编号以及出现次数

题意: 仍旧是天朝语题。 Input 第一行,一个整数N(1<=N<=1000),表示病毒特征码的个数。 接下来N行,每行表示一个病毒特征码,特征码字符串长度在1—50之间,并且只包含“英文大写字符”。任意两个病毒特征码,不会完全相同。 在这之后一行,表示“万恶之源”网站源码,源码字符串长度在2000000之内。字符串中字符都是ASCII码可见字符(不包括回车)。

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

C语言:柔性数组

数组定义 柔性数组 err int arr[0] = {0}; // ERROR 柔性数组 // 常见struct Test{int len;char arr[1024];} // 柔性数组struct Test{int len;char arr[0];}struct Test *t;t = malloc(sizeof(Test) + 11);strcpy(t->arr,

C 语言基础之数组

文章目录 什么是数组数组变量的声明多维数组 什么是数组 数组,顾名思义,就是一组数。 假如班上有 30 个同学,让你编程统计每个人的分数,求最高分、最低分、平均分等。如果不知道数组,你只能这样写代码: int ZhangSan_score = 95;int LiSi_score = 90;......int LiuDong_score = 100;int Zhou

遮罩,在指定元素上进行遮罩

废话不多说,直接上代码: ps:依赖 jquer.js 1.首先,定义一个 Overlay.js  代码如下: /*遮罩 Overlay js 对象*/function Overlay(options){//{targetId:'',viewHtml:'',viewWidth:'',viewHeight:''}try{this.state=false;//遮罩状态 true 激活,f

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图

计算数组的斜率,偏移,R2

模拟Excel中的R2的计算。         public bool fnCheckRear_R2(List<double[]> lRear, int iMinRear, int iMaxRear, ref double dR2)         {             bool bResult = true;             int n = 0;             dou

C# double[] 和Matlab数组MWArray[]转换

C# double[] 转换成MWArray[], 直接赋值就行             MWNumericArray[] ma = new MWNumericArray[4];             double[] dT = new double[] { 0 };             double[] dT1 = new double[] { 0,2 };