如何快速的找出重复的数?

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

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

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

Geo5
Geo5
463
编辑于2012-03-08
评论 (6)链接2012-03-08 
  • 1 支持
    你说的前提做法时间复杂度是O(N),更好的方案只能是低于O(N),给出一个限定条件吧,如果是有序连续,可以到Log(N),如果是不连续,可以尝试考虑变种一下二分法再加上map试试,就算这样,感觉也是能降低常数项,没法在数量级上做文章了。 – 王辉 2012-03-08
  • 0 支持
    这个问题我是想拿来讨论一下的,是以前我去一家公司的面试题,我给的答案就是我问答里说的,但是人家不太满意,所以才在这里求更好的解决方案。 – 浪际天涯 2012-03-08
  • 0 支持
    是不是出题的理解错了,根源题目似乎是google的一道算法题:Find the repeated numbers in a sorted array using less than O(n) time complexity. So, if you have, A[] = {1,1,1,2,2,2,3,3,4},you should print, 1=>3, 2=>3, 3=>2, 4=>1. – 王辉 2012-03-08
  • 0 支持
    题我应该没有记错,因为这个题给我印象很深刻,但他们公司有没有出错题我就不知道了 – 浪际天涯 2012-03-08
显示更多隐藏的评论

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (4)链接 • 2012-03-08
  • 0 支持
    我问的是算法,不是说用PHP或者用C已有的函数去实现,你这个答案相当于把工作交给PHP去做了。 – 浪际天涯 2012-03-08
  • 0 支持
    你没有说要算法。你的算法的效率也不会比php原生函数快 – 大人 2012-03-08
  • 0 支持
    好吧,是我发问题的时候选错了问答类型,我现在想问的不是算法会不会比谁的快,我这里说的是单纯的算法,不限什么来实现算法。就好比面试的时候人家让写一道冒泡算法,你直接用PHP的sort()函数解决了,那肯定得零分。 – 浪际天涯 2012-03-08
  • 1 支持
    如果你不讨论算法会不会比谁快,那最简单的就是最好的,赞成你的前提答案。 – 王辉 2012-03-08
该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (2)链接 • 2012-03-08
  • 0 支持
    感谢提供,但是这个跟我的要求不一样 – 浪际天涯 2012-03-08
  • 0 支持
    嗯。思路可以借鉴一下。。。 – 孙晋硕 2012-03-08

可以参考贝叶斯概率的思路。首先考虑这批数据是否符合某个分布?假如是满足某种分布的,则可以通过二分,优先搜索命中概率大的区域。如果是用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。但是对某些数据有可能特别适合,比如非常均匀的大样本数据。

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-09-19

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-09-20

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

该答案已被锁定,无法对其进行评论,编辑及投票。
()
评论 (0)链接 • 2012-09-24
德问是一个专业的编程问答社区,请 登录注册 后再提交答案