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个缺失的数本质上是一样的 : 可以互相作为变化的形式出现。
|