Google fulltime 电面

firemanysome 发表于 2016-3-26 00:29
这个题的最佳时间复杂度是nlogn吗？

不是。 是2^k, where 1 <= k = x.size() <= 10

hesha0987 发表于 2016-2-25 12:22
贴错代码了。。。是下面这个：
    int res = (1 + N)*N/2;
    sort(X.begin(), X.end());

如果X是{2, 3, 5}那你这算法就会多减一个10

song4you 发表于 2016-2-27 03:52
我去。 膜拜大神！！我按你的公式写出来了! 我试了下worst case， 这个公式秒出答案， kn等了好几分钟。 ...

楼主方便贴一下代码吗？
“k个primes 数的sum”到底什么意思？

zddllc 发表于 2016-2-26 04:35
感觉就是leetcode的 super ugly number.
求出小于n的super ugly number, 然后求和的时候不考虑这些ugly nu ...

是的 我也感觉是super ugly number的做法

stefan0428 发表于 2016-2-25 14:32
可不可以先求出总和 然后根据X 求出小于N的所有丑数， 然后在减掉

也想说这个方法是O(N)，感觉是比较优的解

stefan0428 发表于 2016-2-25 14:32
可不可以先求出总和 然后根据X 求出小于N的所有丑数， 然后在减掉

也想说这个方法是O(N)，感觉是比较优的解

stefan0428 发表于 2016-2-25 14:32
可不可以先求出总和 然后根据X 求出小于N的所有丑数， 然后在减掉

也想说这个方法是O(N)，感觉是比较优的解