有100万个数字（1到9），其中只有1个数字重复2次，如何快速找出该数字

starwing83

1到9？100万？那么每个数字至少得出现10万次吧？？

starwing83

遍历一遍, 关健是遍历过程中, 每新发現一个肯定不是解,就时刻注意当前还可能为解的数目.
极端情形下,没啥好 ...
peidright 发表于 2011-08-04 09:17

    你在O(1)的空间下，能做到O(n)的复杂度？？在没有特殊的算法的前提下（如异或）可能么？

starwing83

回复 7# peidright


    如果只有1~9九个数字，肯定没意义，我回过了，但是假设有999999个各不相同的32位数，有一个数字和前面的一个数字重复，请问如何找到这个重复的数字呢？

starwing83

回复 9# peidright


    是这样的，我以前好像看过类似的题目，有一个很巧妙的异或的解法。我去matrix67的博客找找……

starwing83

回复 10# starwing83


    我记错了…………那个解法是针对求仅有一个数出现过奇数次的…………

starwing83

回复 15# hidensu


    这位大神请问您知道啥叫时间复杂度吗？

starwing83

回复 17# hidensu


    “很大提高效率”？有测试过？常数多少？具体算法？你以为只两个两个比就可以了？这个世界上不是所有的划分算法都是可以两个两个比的。

starwing83

LS：您的方法都要求空间复杂度O(N)，我想知道能不能在空间复杂度O(1)的前提下搞定

starwing83

回复 32# cjaizss


    很有趣的问题：偶选奇可以用异或法达到O(1)的空间复杂度和O(n)的时间复杂度，然而嘛……奇选偶却无法用O(1)的空间复杂度达到O(n)的时间复杂度？？这个是什么原因呢？