Wish phone interview挂经

eshang 发表于 2019-1-22 04:37
哦吼吼我反而觉得考官更喜欢看你用内置吧这样不用重复造轮子。。不过无所谓了，楼主加油哦
PS: 为啥我越 ...

我刚刚仔细想了想，divide and conquer的确是有限空间下sort的最优解（古人诚不欺我），因为同样是O（nlogk），用merge sort的多项式n前面的系数会比用priority queue小一点，因为merge sort里面第一遍就把一半的顺序排好了，这时候每个数字的操作次数是k，但是priority queue把一半排好的时候已经有一半都扔进去了，这时候的操作次数已经打到log(n/2)*k了。

你可以先固定有n个k个数字的list，手动把这两种O（nlogk）的polynomial算出来看看

补充内容 (2019-1-22 05:55):
nvm，我刚刚想成把所有都推到一个priority queue里了，也可以先分开来推到不同的queue里分治

楼主你这个是全职么。方便说下啥组么

xoo123456 发表于 2019-1-22 05:57
楼主你这个是全职么。方便说下啥组么

全职。。好像是叫platform组

消逝一风 发表于 2019-1-22 05:46
我刚刚仔细想了想，divide and conquer的确是有限空间下sort的最优解（古人诚不欺我），因为同样是O（nlo ...

楼主， 我也在加拿大， 加个微信？ 我私信你了

楼主能问下二分法咋做的么

xoo123456 发表于 2019-1-23 06:01
楼主能问下二分法咋做的么

你搜下 merge sort网上全是

消逝一风 发表于 2019-1-23 06:10
你搜下 merge sort网上全是

不是我意思第一题目。。int要变成string么，不变成string是不是得用log10()判断数字长度呀,谢谢。。

xoo123456 发表于 2019-1-23 06:18
不是我意思第一题目。。int要变成string么，不变成string是不是得用log10()判断数字长度呀,谢谢。。

哦哦，就是先log一下看看多少位数，比如有十位数，先mod10^5，如果0就去掉再做，没有就mod10^2的二分

哦哦谢谢了，我是每次mod长度的一半，，为啥要mod10^5。。

xoo123456 发表于 2019-1-23 06:24
哦哦谢谢了，我是每次mod长度的一半，，为啥要mod10^5。。

“比如有十位数”，就是举个例子