11/10 脸书全职挂经 非leetcode题！！！！！！！！！！

白人小哥 直接做题 hello都没说 给一个array 比如 [9,9,5,3,3,7,1] 里面的数字都是0到9之间 inclusive 给你个k 给出top k largest number sum

比如 top 3 = 9+9+7

讨论就讨论了20分钟 我先说用priorityqueue 扫一

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

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

了一下要用bucket sort或radix sort。。 哪位大神来解释一下。。。

找工作不容易 求问犬只挂了还能申请实习吗 换个名字邮箱有用吗。。

如果都用heap的话 add n次 + poll k次 复杂度是nlogn + klogn = (n + k)logn

如果用bucket sort n个元素排序是 n, 拿k个出来是常数复杂度, 因为只有0-9十个数字 所以复杂度是n

public int topkSum(int[] nums, int k) {
        int[] counter = new int[10];
        for(int num : nums) {
            counter[num - 0]++;
        }
        int kSum = 0, remain = k;
        for(int i = 9; i >= 0 && remain > 0; i--) {
            if(remain >= counter[i]) {
                kSum += counter[i] * i;
                remain -= counter[i];
            } else {
                kSum += remain * i;
                break;
            }
        }
        return kSum;
    }

woshilindan 发表于 2017-11-11 16:37
对在哪里 不是跟priorityqueue做法一样的吗 都要先遍历原数组一遍 如果原数组1有1 million个不是很浪费时 ...

我问你如果k非常大，你的pq空间复杂度是多少。你的时间复杂度也是nlogk。k很大就几乎nlogn了。用array空间是常数，时间复杂度是o(n)。

小哥的意思是不是你用pq太费空间了？
你只用array记录然后直接根据k返回结果就可以了。
比如test case是{9,9,5,3,3,7,1}，对应的array就是{0,1,0,2,0,0,0,1,0,2}
k=3从大往小返回就可以了，先是2个9，然后没有8，然后1个7

楼主后来的做法是对的呀

所以这题不是leetcode那道top k largest number？只是从求top k largest numbers 变成求top k largest numbers的sum了吧？道理不应该还是那个道理么。先count frequency存到hashmap里，然后bucket sort hashmap values，然后求top k的sum。是我哪里没想到吗？

补充内容 (2017-11-11 18:18):
啊看错题了_(:з」∠)_
确实不是leetcode题。不好意思。

0-9之间这么小的范围算是挺明显的bucket或者radix sort暗示了吧，算法课只要讲到基本都会这么考，当然counting sort也行啊

这是面经原题, 之前 mitbbs 报过

同问，fb全职挂了还能投实习么？

ls2882177 发表于 2017-11-11 13:42
小哥的意思是不是你用pq太费空间了？
你只用array记录然后直接根据k返回结果就可以了。
比如test case是{ ...

priorityqueue和array不都是一样的复杂度？到要先扫一遍？？？

cutehuazai 发表于 2017-11-11 13:47
楼主后来的做法是对的呀

对在哪里 不是跟priorityqueue做法一样的吗 都要先遍历原数组一遍 如果原数组1有1 million个不是很浪费时间？？？