r**u
发帖数: 1567 | 1 一个数组中存放N个整数，如何找到出现次数最多的一个数（即众数），要求用O(N)的
复杂度，而且不能用Hashing（内存和时间都是O（N））。
Any new thoughts? |
m*****f
发帖数: 1243 | 2 内存O（N)???
Do you mean O(1)?
If has O(n) memory, count sort, bucket sort, radix sort all can do it ba. |
r**u
发帖数: 1567 | 3 O(N)。你这个不对吧，count sort要知道range，这个range可以是0-2^31-1。不是O(N)。bucket也不对吧。
radix我明白了，对的。
【在 m*****f 的大作中提到】
: 内存O（N)???
: Do you mean O(1)?
: If has O(n) memory, count sort, bucket sort, radix sort all can do it ba.
|
r********g
发帖数: 1351 | 4 不好意思我google了一下，发现这道题很trick，因为在实际运算中很难handle x^y这
种运算吧，很容易溢出？
这里假设数组的值都比较小的情况下，然后遍历一遍把数组的信息记录在一个大的数里
。比如,一个弱智的方法是，比如所有的数字都小于10，可以记录在一个digit里，然后
用一个N位数记录每个数字出现的次数。
如果数值不局限于0-9，可以用SUM_i(N^a[i])
N)
【在 r**u 的大作中提到】
: O(N)。你这个不对吧，count sort要知道range，这个range可以是0-2^31-1。不是O(N)。bucket也不对吧。
: radix我明白了，对的。
|
m*****f
发帖数: 1243 | 5 You assume these conditions...
I am just saying these methods are O(N), use what depends on communication
with the interviewer..isn't it?
N)。bucket也不对吧。
【在 r**u 的大作中提到】
: O(N)。你这个不对吧，count sort要知道range，这个range可以是0-2^31-1。不是O(N)。bucket也不对吧。
: radix我明白了，对的。
|
H*M
发帖数: 1268 | 6 I guess the original question is that the time that number appears is more t
han N/2. If that is the case, yeah, you can solve it in o(N).
【在 r**u 的大作中提到】
: 一个数组中存放N个整数，如何找到出现次数最多的一个数（即众数），要求用O(N)的
: 复杂度，而且不能用Hashing（内存和时间都是O（N））。
: Any new thoughts?
|
c*****o
发帖数: 178 | 7 被问到，要求不可以用extra space,但是没有复杂度限制，我就说quick sort O(nlgn)
.然后考官说你知道big O？你哪里学的？汗，对我这非cs的期待好低。。。。。。 |
r**u
发帖数: 1567 | 8 That is a different question!
mudhoof说的radix sort solution是对的吧？did I miss something? 不过我觉得count/bucket sort不对。
t
【在 H*M 的大作中提到】
: I guess the original question is that the time that number appears is more t
: han N/2. If that is the case, yeah, you can solve it in o(N).
|
H*M
发帖数: 1268 | 9 practically radixsort的efficiency并不好吧
const太大
count/bucket sort不对。
【在 r**u 的大作中提到】
: That is a different question!
: mudhoof说的radix sort solution是对的吧？did I miss something? 不过我觉得count/bucket sort不对。
:
: t
|
