w*********6
发帖数: 114 | 1 有一个数组有M个元素，没有sort的，找出最大的N个数的和，但是N个数是可以重复的
，例如A= 【2,9,3,9,1,7,8,2,8,9】， N= 2， 结果是9*3 + 8*2 = 43. 要求时间O(M)
。请问大家怎么做？
谢谢大家 |
l*****7
发帖数: 55 | 2 能先拿个hash map过一遍吗？之后再对hasp map 的keys进行partition。
应该有更好的办法。
M)
【在 w*********6 的大作中提到】
: 有一个数组有M个元素，没有sort的，找出最大的N个数的和，但是N个数是可以重复的
: ，例如A= 【2,9,3,9,1,7,8,2,8,9】， N= 2， 结果是9*3 + 8*2 = 43. 要求时间O(M)
: 。请问大家怎么做？
: 谢谢大家
|
w*********6
发帖数: 114 | 3 面试的人说不需要用hashtable...
【在 l*****7 的大作中提到】
: 能先拿个hash map过一遍吗？之后再对hasp map 的keys进行partition。
: 应该有更好的办法。
:
: M)
|
a*********4
发帖数: 7 | 4 how about using a minQ/minHeap with size N? but that would have O(MlogN)
time, not exactly O(M)
【在 l*****7 的大作中提到】
: 能先拿个hash map过一遍吗？之后再对hasp map 的keys进行partition。
: 应该有更好的办法。
:
: M)
|
l****i
发帖数: 2772 | 5 partition, selection algorithm. |
z****e
发帖数: 54598 | 6 元素本身的值也就是89那些
跟
数组长度有对应关系没？
是不是数组元素的值都<数组长度？ |
m****s
发帖数: 131 | 7 如果不能用额外空间。用partition找到前N大的数字。。
如果可以用额外空间，用一个set之类的排序的容器把前N大的数字在一次扫描后存储下
来。。。 |
y**********a
发帖数: 824 | |
g***j
发帖数: 1275 | 9 如果有重复的怎么找前n大的数？
【在 m****s 的大作中提到】
: 如果不能用额外空间。用partition找到前N大的数字。。
: 如果可以用额外空间，用一个set之类的排序的容器把前N大的数字在一次扫描后存储下
: 来。。。
|
n*****n
发帖数: 5277 | 10 重复的数算一个
【在 g***j 的大作中提到】
: 如果有重复的怎么找前n大的数？
|
|
|
w*********6
发帖数: 114 | 11 好像还真说了数组元素在0~9之间。这个有关系？我还真没意识到哟。。。
但长度可以很短。
【在 z****e 的大作中提到】
: 元素本身的值也就是89那些
: 跟
: 数组长度有对应关系没？
: 是不是数组元素的值都<数组长度？
|
w*********6
发帖数: 114 | 12 我擦。。。不会是用个数组统计一下0~9的每个数出现的次数就可以了吧。。。多谢提
醒。。。
【在 z****e 的大作中提到】
: 元素本身的值也就是89那些
: 跟
: 数组长度有对应关系没？
: 是不是数组元素的值都<数组长度？
|
y**********a
发帖数: 824 | 13 int max(int[]A, n) {
Map m=new HashMap<>();
for (int a:A)
if (!m.containsKey(a)) m.put(a,a);
else m.put(a, m.get(a)+a);
int[] B=new int[m.size()];
int i=0;
for (int key:m.keySet()) B[i++]=m.get(key);
int k=quickSelect(B, n), c=n, s=0;
for (int i=0;i=B[k]) s+=B[i];
return s+c*B[k];
} |
n****o
发帖数: 239 | 14 复杂度要求O(M)的话，还是要用Hashtable吧。 |
T*****u
发帖数: 7103 | |
r*******k
发帖数: 1423 | 16 ft，这不是太弱智了么
数组sum[10]
碰到i，就累加到sum[i]去
然后这10个数找最大的两个
【在 w*********6 的大作中提到】
: 好像还真说了数组元素在0~9之间。这个有关系？我还真没意识到哟。。。
: 但长度可以很短。
|
