找到最常输入C的数字的最佳(最快)方式？

Question

好吧,我认为标题基本上解释了我的怀疑.我将有n个数字来读取,这n个数字从1到x,其中x最多为10 ⁵.什么是最快(运行它的可能时间较短)的方式来找出插入的次数是多少？那知道,出现次数最多的数字出现较次的一半以上.

到目前为止我尝试过的:

//for (1<=x<=10?)
int v[100000+1];

//multiple instances , ends when n = 0
while (scanf("%d", &n)&&n>0) {
    zerofill(v);
    for (i=0; i<n; i++) {
        scanf("%d", &x);
        v[x]++;
        if (v[x]>n/2)
            i=n;
    }
    printf("%d\n", x);
}

零填充x位置的数组并增加位置向量[x],同时验证向量[x]是否大于n/2,它不够快.

任何想法都可能有所帮助,谢谢.

观察:无需关心使用的内存量.

Answer 1

保持计数器阵列的简单解决方案是O(n),你显然不能比这更好.战斗是那么有关的常数,这是很多的细节必玩的游戏,包括什么是价值n和x什么样的处理器,什么样的架构等等.

另一方面,这似乎真的是"淘汰"问题,但该算法需要两次传递数据和一个额外的条件,因此在计算机的实际条件下,我知道它最可能比计数器解决方案的数组慢.很多n和x价值观.

淘汰赛解决方案的优点是您不需要x对值进行限制,也不需要任何额外的内存.

如果您已经知道存在绝对多数的值(并且您只需要找到该值是什么)那么这可以实现(但内部循环中有两个条件):

• 初始化 count = 0
• 遍历所有元素
• 如果count被0然后设置champion = element与count = 1
• 否则如果element != champion减少count
• 否则增加 count

在循环结束时champion,如果存在这样的值,则将使用绝对多数元素的值.

但正如之前所说,我期待一件小事

for (int i=0,n=size; i<n; i++) {
    if (++count[x[i]] > half) return x[i];
}

更快.

编辑

你编辑之后似乎真的在寻找淘汰赛算法,但关心速度这可能仍然是现代计算机的错误问题(今天100000元素甚至对于钉子大小的单芯片来说都没有).