主元素问题
概述
给一个有
做法
桶计数做法
桶计数做法是出现一个数,就把这个数出现次数
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;
}
}
时间复杂度
但是这个做法很浪费空间,我们不推荐使用。
排序做法
显然,若一个数列存在主元素,那么这个主元素在排序后一定位于
那么我们又有想法了:
看起来不错!
下面介绍本问题的
主元素数列的特性
由于主元素的出现的次数超过
输入时判断与上一次保存的输入是否相同,如不同则删除两数,这里用栈来实现。
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]);
再进行优化后,空间复杂度也可以降至
int val = -1, cnt = 0;
while (n--) {
scanf("%d", &a);
if (a != val) {
if (--cnt <= 0) {
val = a, cnt = 1;
}
} else {
++cnt;
}
}
最后更新: February 13, 2022
创建日期: January 4, 2021
创建日期: January 4, 2021