算法-如何快速的找出重复的数?

算法-如何快速的找出重复的数?

偏爱自由 发布于 2017-08-06 字数 497 浏览 1288 回复 5

现在有序但不连续的1,000,000个数,其中只有一个数是重复的,如何快速高效的找出这个重复的数?

前提:遍历所有数,将当前数和它右边一个数进行比较,它们相等即这个数就是所要找的数,这个是最简单的方法,大家就不要说了,说说其它更好的方案吧。

我补充说明一下:出这个题的目的是曾经有人对我这个答案不太满意,所以才来寻求更好的答案,还有一个就是这里讨论的是纯算法,请不要用PHP、C、C++等语言已有的功能函数来实现,我们不跟他们比快,这里只讨论用单纯的算法实现起来有没有比我说的那个更好的方案。

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(5

泛泛之交 2017-10-08 4 楼

可以参考贝叶斯概率的思路。首先考虑这批数据是否符合某个分布?假如是满足某种分布的,则可以通过二分,优先搜索命中概率大的区域。如果是用random产生的,可以看作是均匀分布的。理论上,这样可以得到最坏情况为O(N)的复杂度,但是一般应该要好一些。有效的原理是优先搜索命中概率高的区域。

举例:
最小的数是1,最大数是2,000,001,则中位数是1,000,001。探查下标为500,000的元素,如果比1,000,001小,说明左侧数据密集,重复概率大,优先搜左侧。反之优先搜右侧。
或许还可以继续改进,例如将左侧的数据范围/元素个数记为数据密度,当右侧在二分搜索的时候,不必等到搜完了再处理左边,而是优先处理密度最大的区间:
1.准备一个优先队列,以数据密度排序,同时附加记录对应区间的起止下标。
2.二分当前区间,计算数据密度和区间范围。密度为0则找到,结束。不可分则转到5
3.比较两者数据密度,小的入队列
4.和队列首元素比较,如果密度比队列中的大,转到步骤2否则也入队
5.队列空,数据不满足条件,即没有重复,
2.弹出首元素,转步骤2.

但这个改进算法的最坏复杂度是NlogN的,因为优先队列插入元素的复杂度是LogN。但是对某些数据有可能特别适合,比如非常均匀的大样本数据。

归属感 2017-09-19 3 楼

像set这样的 不允许相同键的关联容器添加...然后如果添加失败 说明找到重复的了

晚风撩人 2017-08-28 2 楼

我看明白你的问题了, 从小到大但不连续的1000000个数字,找到重复的那个数字。
假设你的数据是一个数组
$nums = array(1,2,3,4...,677821,677821,...);
思路一
array_count_values 后 sort
思路二
array_unique后array_diff

晚风撩人 2017-08-24 1 楼

可以证明最坏情况下复杂度至少是O(n)
设想1,2,...,1000000
这个数组中,任选一个数k (k>1)替换成k-1,就符合题目条件了
这样一共有999999种不同的情况。
对任意符合题目要求的算法,应该能在算法结束时区分出这999999种不同情况;
而同时,任取至多999998个位置,都存在至少两种不同的情况,使得这999998个位置上的数完全相同,而最终结论不同
这说明这一算法至少需要访问999999个不同的位置。因此最坏情况下算法复杂度不可能好于O(n)。