Wepay OA面经及讨论

jy02535954 发表于 2017-9-2 12:50
没事了 我改了代码以后全过了   NlogN....   好爽 哈哈哈哈

有思路的话求分享一下

用堆排序，Java的话就用PriorityQueue。用一个Set判断每次向queue中添加的数字是否重复，不重复则添加。
两层for循环求power number，底数i从2增加到index+3，指数j从2增加到20几应该就够了。
再把queue poll到第index个元素。希望有帮助

感觉LZ这个for循环的写法不太对，这样会把很多不是power number的数字也纳入了检查的范围。因为LZ是先计算了一个power number放入map里，然后跑循环，如果发现这的确是计算过的power number，才会--index，比如题目要求的答案是25，那么计算5*5的时候其实就完了，但按这个for循环来看的话还会跑6,7...25这样跑多了很多循环。

刚做了一下，用PQ+一点小优化就全过了…

Regulus 发表于 2017-9-3 03:50
用堆排序，Java的话就用PriorityQueue。用一个Set判断每次向queue中添加的数字是否重复，不重复则添加。
...

不需要额外的set.  一个固定长度PQ就够了  O(nlogn) 时间  O(1)空间

nagisafight 发表于 2017-9-2 15:11
可以提供一下思路吗？谢谢

思路就是super ugly number 那题优化
一个PQ, 建一个数据结构  O(1)空间 O(nlogn).  具体代码我拿到电面贴给你们

无量塔 发表于 2017-9-3 06:28
刚做了一下，用PQ+一点小优化就全过了…

请问怎么优化的呢，我也刚做完，最后两个case不过。用的是PQ+hashset去重，PQ用了reverseOrder(),还是过不了最后两个case

llzy1178 发表于 2017-9-3 07:32
请问怎么优化的呢，我也刚做完，最后两个case不过。用的是PQ+hashset去重，PQ用了reverseOrder(),还是过 ...

可以根据给出来的index找一个最小的上界，最终答案只会小于等于这个上界。跑循环的时候，计算出来的power number大于这个上界就换个base再计算，至于上界怎么找就需要自己稍微思考一下了：）
另外的就跟帖子里另一个兄弟一样保持固定大小的pq。

你们讨论那么久，是不是实现有问题，用priority queue 本身就是一遍AC啊，单步迭代由线性搜索弄为了log级别的，是不是哪里有问题了才不过case…

我还在想是不是可以利用某种数学性质类似用binary search 的方法搜第k个，就是不用从1开始一个个搜到k，结果一般的priorityqueue提交就AC了。。。。