主元素问题与摩尔投票法、格雷码
2022/9/3 23:23:35
本文主要是介绍主元素问题与摩尔投票法、格雷码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一堆小玩意,放到一起。
题意:给定一个n个元素数列,保证有一个数\(a\)的出现次数超过\(\lfloor\frac n2 \rfloor\),求这个数。
数据范围\(n<=3000000,a_i\le2147483647,\)时限0.5s,空间2M。
也就是说你就只开几个变量就行了。(虽然考试的时候有人拿hash玄学乱搞过了)
首先这个时间卡掉了排序,空间和数据范围卡掉了桶的做法。我们考虑利用“数\(a\)的出现次数超过\(\lfloor\frac n2 \rfloor\)”这个特性。
我们发现(反正我没发现我太弱了55555)如果两两删去两个不同的元素,最后剩下的一定是元素\(a\)。证明考虑最坏的情况,所有其他元素一起来删掉\(a\),那么由于\(a\)的个数超过一半,一定可以删掉其他所有的元素而自身有保留元素。
于是我们就得到了一种\(O(n)\)模拟的方法,而且只需要四个\(int\)变量:\(n\),输入的\(x\),计数器\(cnt,ans\)。具体地,我们每次输入一个数的时候,进行如下操作:
- 如果\(cnt=0\),则用\(x\)更新\(ans\),将\(cnt\)设为\(1\)。
- 如果\(x\ne ans\),则将当前计数器\(cnt-1\)。(也就是用不同的元素互相消去)
- 反之\(cnt+1\)。(也就是统计相同的元素个数)
依题意模拟即可。
scanf("%d",&n); while(n--){ int x;scanf("%d",&x); if(ans!=x){ if(--cnt<=0)ans=x,cnt=1; } else cnt++; }
反正我觉得不会考,但是考了就考了吧。
格雷码是一个二进制数系,其中两个相邻数的二进制位只有一位不同。
给出手动构造方法:
- 翻转最低位得到下一个格雷码。
- 翻转最右边的1的左边一位得到下一个格雷码。
交替操作1,2共\(2^{k-1}\)次可得到k位的格雷码序列。举个例子,3位格雷码序列为:
\[000,001,011,010,110,111,101,100 \]注意我们说的格雷码下标是从0开始的,即\(G(0)=000,G(4)=110\)。
然后是计算法:第\(n\)位格雷码为:
\[G(n)=n \oplus \lfloor\frac n2\rfloor \]int g(int n){ return n^(n>>1); }
然后是它的逆变换。\(n\)的二进制第\(i\)位与其格雷码\(g\)的二进制第\(i\)位的关系(最高位为\(k\)):
\[n_{k-i}=\bigoplus_{j=0}^ig_{k-j} \]int getn(int g){ int n=0; for(;g;g>>=1)n^=g; return n; }
这篇关于主元素问题与摩尔投票法、格雷码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26敏捷开发:想要快速交付就必须舍弃产品质量?
- 2024-04-26静态代码分析的这些好处,我竟然都不知道?
- 2024-04-26你在测试金字塔的哪一层?(下)
- 2024-04-26快刀斩乱麻,DevOps让代码评审也自动起来
- 2024-04-262024年最好用的10款ER图神器!
- 2024-04-2203-为啥大模型LLM还没能完全替代你?
- 2024-04-2101-大语言模型发展
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding