第二十一章:数组中超过出现次数超过一半的数字

2024-02-01 05:18

本文主要是介绍第二十一章:数组中超过出现次数超过一半的数字,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

第二十一章数组中出现次数超过一半的数字

题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。 


//题目:数组中有一个数字出现的次数超过了数组长度的一半,找出这个数字。 
#include <iostream>  
#include <vector>
#include <hash_map>  using namespace std;  //第一种方法
//hash法,时间O(n),空间O(n)
int Find(int *a,int N){hash_map<int,int> hm;int candidate;int maxTimes=INT_MIN;for(int i=0;i<N;i++){hm[a[i]]++;if(hm[a[i]]>maxTimes){maxTimes=hm[a[i]];candidate=a[i];}}return candidate;
}//第二种方法
//统计法,时间O(n),空间O(1)
int Find2(int *a, int N)  //a代表数组,N代表数组长度  
{  int candidate;  int nTimes, i;  for(i = nTimes = 0; i < N; i++)  {  if(nTimes == 0)  {  candidate = a[i], nTimes = 1;  }  else  {  if(candidate == a[i])  nTimes++;  else  nTimes--;  }  }  return candidate;   
}  //第三种方法
//删除法,因为涉及到删除,数组不好操作,所以用容器处理
int Find3(int *a,int N)  //a代表数组,N代表数组长度  
{  vector<int> num(a,a+N);for(auto it=num.begin();it!=num.end();){auto n=next(it);for(;n!=num.end()&&n==it;++n);if(n==num.end())break;num.erase(n);it=num.erase(it);}return *num.begin();
}  
int main()  
{  int a[]={4,5,6,5,5,4,7,5,5};cout<<Find3(a,sizeof(a)/sizeof(int))<<endl;
}  

加强版水王:找出出现次数刚好是一半的数字


//题目:找出出现次数刚好是一半的数字 
#include <iostream>  
#include <vector>
#include <hash_map>  using namespace std;  //第一种方法
//统计法,时间O(n),空间O(1)
//将不看数组的最后一个元素,先将问题转化成了超过一半的数处理
//最后一个元素无外乎两种情况,一种是最后一个元素不是这等于一半的数,那就不予考虑,以上得出的即是答案
//最后一个元素即是这等于一半的数,上面得出的就不一定是解,那就统计该元素出现的次数
int Find(int *a, int N)  //a代表数组,N代表数组长度  
{  int candidate;  int nTimes, i;  for(i = nTimes = 0; i < N; i++)  {  if(nTimes == 0)  {  candidate = a[i], nTimes = 1;  }  else  {  if(candidate == a[i])  nTimes++;  else  nTimes--;  }  }  int cnt=0;for(int i=0;i<N;i++)if(a[i]==candidate)cnt++;return cnt==N/2?candidate:a[N-1];   
} //第二种方法
//两个变量记录法
int Find2(int *a,int N){int candidate1,candidate2;  int nTimes1, nTimes2, i;  for(i = nTimes1 = nTimes2 =0; i < N; i++)  {  if(nTimes1 == 0)  {  candidate1 = a[i], nTimes1 = 1;  }  else if(nTimes2 == 0 && candidate1 != a[i])  //注意:这里的判断条件加上第二个变量是否等于第一个变量的判断  {  candidate2 = a[i], nTimes2 = 1;  }  else  {  if(candidate1 == a[i])  nTimes1++;  else if(candidate2 == a[i])  nTimes2++;  else  {  nTimes1--;  nTimes2--;  }  }  }  return nTimes1>nTimes2?candidate1:candidate2;
}
int main()  
{  int a[]={7,5,6,5,5,7,7,5};cout<<Find2(a,sizeof(a)/sizeof(int))<<endl;
}  




这篇关于第二十一章:数组中超过出现次数超过一半的数字的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

从去中心化到智能化:Web3如何与AI共同塑造数字生态

在数字时代的演进中,Web3和人工智能(AI)正成为塑造未来互联网的两大核心力量。Web3的去中心化理念与AI的智能化技术,正相互交织,共同推动数字生态的变革。本文将探讨Web3与AI的融合如何改变数字世界,并展望这一新兴组合如何重塑我们的在线体验。 Web3的去中心化愿景 Web3代表了互联网的第三代发展,它基于去中心化的区块链技术,旨在创建一个开放、透明且用户主导的数字生态。不同于传统

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

usaco 1.2 Name That Number(数字字母转化)

巧妙的利用code[b[0]-'A'] 将字符ABC...Z转换为数字 需要注意的是重新开一个数组 c [ ] 存储字符串 应人为的在末尾附上 ‘ \ 0 ’ 详见代码: /*ID: who jayLANG: C++TASK: namenum*/#include<stdio.h>#include<string.h>int main(){FILE *fin = fopen (

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码可见字符(不包括回车)。

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

计算数组的斜率,偏移,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 };

PHP7扩展开发之数组处理

前言 这次,我们将演示如何在PHP扩展中如何对数组进行处理。要实现的PHP代码如下: <?phpfunction array_concat ($arr, $prefix) {foreach($arr as $key => $val) {if (isset($prefix[$key]) && is_string($val) && is_string($prefix[$key])) {$arr[