爆一个从来没见过的bb题，顺便求问下有没有人面过三轮最后一轮是hr的。。。

刚面的bb，遇到了一个从没见过的题，发出来攒个人品：
给一个数列：[6,1,2,2,1,3,3,3,9] 按照数字出现次数从多到少依次打印出数字。同时必须保持数字的原顺序：
比如这题输出：3,1,2,6,

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

有人有过这种奇葩经历么？


补充内容 (2016-2-9 05:07):
刚刚收到邮件，跪了。。。。

[6,1,2,2,1,3,3,3,9]
1. 先统计<数字, 出现的次数>
6 -- 1
1 -- 2
2 -- 2
3 -- 3
9 -- 1
2. bucket(i)表示出现i次的数字序列, 最多也就n个bucket(比n小很多应该...)
bucket(1) -- [6,9]
bucket(2) -- [1,2]
bucket(3) -- [3]
最后结果是[3,1,2,6,9]

顺着遍历，得到各个数的次数，然后radix sort或者count sort对出现次数排序，然后输出即可。耗时O(N)

补充内容 (2016-2-5 07:36):
由于数字的出现次数一定是[1,n]之间的某个数，所以count sort最快

First we build  <number,occurences>, then we scan through list again and build <occurences, List<Integer>>, add number to corresponding list according to occurences. Then we output numbers in List<Integer> in order of occurences, just remember not to output duplicate numbers.

two hashmaps. first for < number,occurences> second for<order, number>  

补充内容 (2016-2-4 16:18):
I misunderstood something...

同意二楼做法。但建议使用这个做法时候和主考官讨论tradeoff。

稳了稳了稳了

多谢楼主分享，一定会offer的！

楼主offer到手了嘛？

借这楼所有大哥吉言。楼主正在心惊胆战的等拒信或者电话。。。。。

AndrewFish 发表于 2016-2-5 07:25
First we build  , then we scan through list again and build , add number to corresponding list accor ...

build <occurences, List<Integer>>的过程就要按照 occurneces 排序吧