WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
杂项简介
复杂度
离散化
离线算法简介
CDQ 分治
整体二分
莫队算法简介
普通莫队算法
带修改莫队
树上莫队
回滚莫队
莫队配合bitset
分数规划
随机函数
随机化技巧
爬山算法
模拟退火
悬线法
计算理论基础
字节顺序
约瑟夫问题
Stern-Brocot 树与 Farey 序列
格雷码
表达式求值
在一台机器上规划任务
主元素问题
26 objects
本站非官方，所收集资源均来源于网络。
主元素问题 - 杂项
author: SDLTF ## 概述 给一个有 $n$ 个元素的数列，保证有一个数 $a$ 出现的次数**超过** $\dfrac n 2$，求这个数。 ## 做法 ### 桶计数做法 桶计数做法是出现一个数，就把这个数出现次数 $+1$，很好懂： ```cpp for(int i = 0;i < n;i ++) { cin >> t; ans[t] ++; } for(int i = 0;i < m;i ++) { // m 为桶的大小 if(ans[i] > n / 2){ cout << i; break; } } ``` 时间复杂度 $O(n+m)$。 但是这个做法很浪费空间，我们不推荐使用。 ### 排序做法 显然，若一个数列存在主元素，那么这个主元素在排序后一定位于 $\dfrac{n}{2}$ 的位置。 那么我们又有想法了： ```cpp sort(a, a + n); cout<<a[n / 2 - 1];//因为这里数组从 0 开始使用，所以需要 -1 ``` 看起来不错！$O(n\log n)$ 的复杂度可还行？ 下面介绍本问题的 $O(n)$ 解法。 ### 主元素数列的特性 由于主元素的出现的次数超过 $\dfrac n 2$，那么在不断的消掉两个不同的元素之后，最后一定剩下主元素。 输入时判断与上一次保存的输入是否相同，如不同则删除两数，这里用栈来实现。 ```cpp while(n--) { scanf("%d",&a); q[top ++] = a; top = (top > 1 && (q[top - 1] != q[top - 2]))?(top - 2) : top; } printf("%d",q[top-1]); ``` 再进行优化后，空间复杂度也可以降至 $O(1)$。 ```cpp int val = -1,cnt = 0; while(n--) { scanf("%d", &a); if(a != val){ if(--cnt <= 0) { val = a, cnt = 1; } } else { ++cnt; } } ```
wiki(I:)
比赛相关
杂项简介
