[合集] 一道CS面试题# JobHunting - 待字闺中
m*n
1 楼
☆─────────────────────────────────────☆
HansLee (迅潇麒麟) 于 (Tue Aug 28 01:45:42 2007) 提到:
一个数组中存放N个整数，如何找到出现次数最多的一个数（即众数），要求用O(N)的
复杂度，而且不能用Hashing（内存和时间都是O（N））。
大家有何见教？ （我有一个初步答案，但不一定最佳，改天给出）
☆─────────────────────────────────────☆
obesepig (Obesepig) 于 (Tue Aug 28 02:08:34 2007) 提到:
If space complexity is O(N), then the question is too trivial(Using a
hashtable).
If the space complexity is O(1), it's kind of tricky and I guess probably
your friend is asked to solve the following questi
HansLee (迅潇麒麟) 于 (Tue Aug 28 01:45:42 2007) 提到:
一个数组中存放N个整数，如何找到出现次数最多的一个数（即众数），要求用O(N)的
复杂度，而且不能用Hashing（内存和时间都是O（N））。
大家有何见教？ （我有一个初步答案，但不一定最佳，改天给出）
☆─────────────────────────────────────☆
obesepig (Obesepig) 于 (Tue Aug 28 02:08:34 2007) 提到:
If space complexity is O(N), then the question is too trivial(Using a
hashtable).
If the space complexity is O(1), it's kind of tricky and I guess probably
your friend is asked to solve the following questi