n******r
发帖数: 1247 | 1 一个数组，所有数重复出现两次，一数出现一次，找出出现一次的数
大家都知道XOR O(N)
如果有两个数出现一次呢？
三个数，四个数，五个数？ 是否有O(N)算法？
最近想到其实这题和一个数组1-N，未排序，O(N)的算法找出k个缺失的数本质上是一样的
可以互相作为变化的形式出现。 |
x*******e
发帖数: 13 | 2 不太一样吧，1-N至少用O（N）space肯定能保证O（N）time
如果不知道数值范围，我觉得会比较困难
【在 n******r 的大作中提到】
: 一个数组，所有数重复出现两次，一数出现一次，找出出现一次的数
: 大家都知道XOR O(N)
: 如果有两个数出现一次呢？
: 三个数，四个数，五个数？ 是否有O(N)算法？
: 最近想到其实这题和一个数组1-N，未排序，O(N)的算法找出k个缺失的数本质上是一样的
: 可以互相作为变化的形式出现。
|
n******r
发帖数: 1247 | 3 sorry，I mean 1-N，unsorted
原题里改了
【在 x*******e 的大作中提到】
: 不太一样吧，1-N至少用O（N）space肯定能保证O（N）time
: 如果不知道数值范围，我觉得会比较困难
|
E*******0
发帖数: 465 | 4 How about using priority queue? |
E*******0
发帖数: 465 | 5 log(1)+log(2)+log(3)+...+log(n)<=n? |
E*******0
发帖数: 465 | |
n******r
发帖数: 1247 | 7 you got 1.5伪币 for the wrong anwser!
【在 E*******0 的大作中提到】
: Sorry. wrong anwser!
|
r**u
发帖数: 1567 | 8 这题应该可以这么做：如果所有的数都>=1，如果重复的数一定重复2次，forall i = 1
-N，A[i] = -A[i]。最后对出现一次i，A[i]是负的，你再go through这个array一遍找
出所有负数的index就行了。
样的
【在 n******r 的大作中提到】
: 一个数组，所有数重复出现两次，一数出现一次，找出出现一次的数
: 大家都知道XOR O(N)
: 如果有两个数出现一次呢？
: 三个数，四个数，五个数？ 是否有O(N)算法？
: 最近想到其实这题和一个数组1-N，未排序，O(N)的算法找出k个缺失的数本质上是一样的
: 可以互相作为变化的形式出现。
|
