g*****1
发帖数: 93 | 1 很多家公司都会问，ex: 有一堆股票，经常更新，要设计数据结构能输出前10名股票。
大概的解法是hashmap + heap，想请大神讲一下具体设计方法 |
c******b
发帖数: 13 | 2 public static List topK(int[] test,int k){
List l = new ArrayList();
if(k>test.length) return l;
//用hash存放股票名称，和出现次数
HashMap hash = new HashMap();
for(int i=0;i
if(hash.containsKey(test[i])){
hash.put(test[i], hash.get(test[i])+1);
} else {
hash.put(test[i], 1);
}
}
//用一个priorityqueue，可以对出现次数进行排序
PriorityQueue> pq = new PriorityQueue
Integer,Integer>>(k, new Comparator>(){
@Override
public int compare(Entry o1,Entry
Integer> o2) {
if(o1.getValue()>o2.getValue()){
return -1;
} else if(o1.getValue()
return 1;
} else {
return 0;
}
}
});
//然后无脑把hash插入到priorityqueue里
pq.addAll(hash.entrySet());
//取出所需要的个数
for(int i=0;i
System.out.println(pq.peek());
l.add((Integer)pq.poll().getKey());
}
return l;
} |
s*******n
发帖数: 344 | 3 大牛
【在 c******b 的大作中提到】
: public static List topK(int[] test,int k){
: List l = new ArrayList();
: if(k>test.length) return l;
: //用hash存放股票名称，和出现次数
: HashMap hash = new HashMap();
: for(int i=0;i: if(hash.containsKey(test[i])){
: hash.put(test[i], hash.get(test[i])+1);
: } else {
: hash.put(test[i], 1);
|
y*********g
发帖数: 8 | 4 感觉不用做一个新的Comparator， hashmap.value(), 然后加到heap里就好了。。 这
题的follow up， 如果进来的是一个stream， 要怎么实时更新heap？ |
w********m
发帖数: 1137 | 5 加个fixed size的queue，随时间滑动。
【在 y*********g 的大作中提到】
: 感觉不用做一个新的Comparator， hashmap.value(), 然后加到heap里就好了。。 这
: 题的follow up， 如果进来的是一个stream， 要怎么实时更新heap？
|
s*******m
发帖数: 228 | 6 能具体讲讲吗
【在 w********m 的大作中提到】
: 加个fixed size的queue，随时间滑动。
|
p**********t
发帖数: 75 | 7 不太明白为什么是记录出现频率，可能是因为我不太懂股票，股票是按出现频率排名的
么？我还以为是数字。。。
【在 c******b 的大作中提到】
: public static List topK(int[] test,int k){
: List l = new ArrayList();
: if(k>test.length) return l;
: //用hash存放股票名称，和出现次数
: HashMap hash = new HashMap();
: for(int i=0;i: if(hash.containsKey(test[i])){
: hash.put(test[i], hash.get(test[i])+1);
: } else {
: hash.put(test[i], 1);
|
p**********t
发帖数: 75 | 8 如果是那种只会一直增加不会减少的（比如出现频率），heap还是比较容易更新的，如
果是数字可以增加也可以减少的那种，要怎么更新heap我就不知道了，有人能说说么
【在 y*********g 的大作中提到】
: 感觉不用做一个新的Comparator， hashmap.value(), 然后加到heap里就好了。。 这
: 题的follow up， 如果进来的是一个stream， 要怎么实时更新heap？
|
z***y
发帖数: 73 | 9 两个问题：
1.经常更新是什么概念？
价格经常更新？成交量经常更新？还是有别的意思？
2.前10名股票是啥概念？
价格最高的前10？成交量最大的前10？价格涨幅最大的前10？ |
g*****1
发帖数: 93 | 10 我有一个问题，在有stream过来需要更新数据时，如果存在在pq里地股票更新了数据要
怎么处理呢？ 是不是通过hashmap track到这个股票然后delete掉再添加到pq里？
【在 c******b 的大作中提到】
: public static List topK(int[] test,int k){
: List l = new ArrayList();
: if(k>test.length) return l;
: //用hash存放股票名称，和出现次数
: HashMap hash = new HashMap();
: for(int i=0;i: if(hash.containsKey(test[i])){
: hash.put(test[i], hash.get(test[i])+1);
: } else {
: hash.put(test[i], 1);
|
|
|
c*****m
发帖数: 271 | 11 不太明白经常更新是啥意思。输出前10的股票用小顶堆是不是就可以？ |
s*********n
发帖数: 35 | 12 前天BB onsite就遇到这道题了，交易会不断的进来，然后getTop10(或者topN)也会频
繁的调用，让设计。 刚开始说priority_queue，对面国人大哥问什么是pq, 改口说
heap，也不让，最后我用双map, 一个map存ticker->{volume, iter_of_rankmap}, 另
一个multimap rankermap, size约束成10，存volumn->ticker, 自圆其说算是解决了
，面试的说cool cool，也不知道是真酷还是忽悠我，至今没想到其他方法。 |
h**********c
发帖数: 4120 | 13 how about it
the source code of top or htop.
【在 s*********n 的大作中提到】
: 前天BB onsite就遇到这道题了，交易会不断的进来，然后getTop10(或者topN)也会频
: 繁的调用，让设计。 刚开始说priority_queue，对面国人大哥问什么是pq, 改口说
: heap，也不让，最后我用双map, 一个map存ticker->{volume, iter_of_rankmap}, 另
: 一个multimap rankermap, size约束成10，存volumn->ticker, 自圆其说算是解决了
: ，面试的说cool cool，也不知道是真酷还是忽悠我，至今没想到其他方法。
|
s*********n
发帖数: 35 | 14 rankermap就是topN
【在 h**********c 的大作中提到】
: how about it
: the source code of top or htop.
|
h**********c
发帖数: 4120 | 15 没太看明白top (built in) in linux 是怎么实现的
【在 s*********n 的大作中提到】
: rankermap就是topN
|
s*********n
发帖数: 35 | 16 哥们儿你捣乱呢么 我在说这道题 和linux里的top没关系
【在 h**********c 的大作中提到】
: 没太看明白top (built in) in linux 是怎么实现的
|
h**********c
发帖数: 4120 | 17 top in linux不就是按cpu usage 列topN吗
还有一个老中contributor 呢，不能现身来讲讲有什么高深算法吗？
一开头看见个 #include 'rbtree.h'，心里疙瘩一下，听说过没用过
【在 s*********n 的大作中提到】
: 哥们儿你捣乱呢么 我在说这道题 和linux里的top没关系
|
s*********n
发帖数: 35 | 18 好吧。。。不好意思 我理解错了，你意思是参考top实现吧
你说用到了rbtree也make sense, map本身就是rbtree，linux用纯c没有stl只能自己实
现了
【在 h**********c 的大作中提到】
: top in linux不就是按cpu usage 列topN吗
: 还有一个老中contributor 呢，不能现身来讲讲有什么高深算法吗？
: 一开头看见个 #include 'rbtree.h'，心里疙瘩一下，听说过没用过
|
h**********c
发帖数: 4120 | 19 ok,
你吃透了top，来讲讲吧
现在没有精力搞
或者前面回贴已经体现了所谓的扁平化的精髓，没太吃透
【在 s*********n 的大作中提到】
: 好吧。。。不好意思 我理解错了，你意思是参考top实现吧
: 你说用到了rbtree也make sense, map本身就是rbtree，linux用纯c没有stl只能自己实
: 现了
|
