c - 查找在 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 位置数组进行零填充并增加位置 vector [x]，同时验证 vector [x] 是否大于 n/2 它不 足够快。

任何想法都可能有所帮助，谢谢。

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

Answer 1

保留计数器数组的简单解决方案是 O(n)，显然没有比这更好的了。争论是关于常量的，这是很多细节将发挥作用的地方，包括 n 和 x 的确切值是多少，什么样的处理器，什么样的架构等等。

另一方面，这似乎是真正的“淘汰”问题，但该算法需要两次传递数据和一个额外的条件，因此在计算机的实际情况下，我知道它很可能比数组慢大量 n 和 x 值的计数器解决方案。

淘汰解决方案的好处是您不需要对值设置限制 x，也不需要任何额外的内存。

如果你已经知道有一个绝对多数的值(你只需要找到这个值是什么)那么这就可以做到(但内部循环中有两个条件):

• 初始化count = 0
• 遍历所有元素
• 如果 count 为 0，则设置 champion = element 和 count = 1
• else if element != champion 递减 count
• 否则增加count

在循环结束时，您的 champion 将是具有绝对多数元素的值(如果存在这样的值)。

但如前所述，我期望一个微不足道的

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

更快。

编辑

在你的编辑之后，你似乎真的在寻找淘汰算法，但关心速度对于现代计算机来说可能仍然是一个错误的问题(100000 个元素即使对于今天的钉子大小的单芯片来说也不算什么)。