狗狗家

hankok 发表于 2018-6-20 11:13
我是dfs层主 才疏学浅，当时看着像DFS 现在发现没用到 你用的dp公式？求赐教

我看了一下，你楼上的帖子跟我的想法一致！！！赞表达！！！

补充内容 (2018-6-20 12:59):
我说的是你这个回复之前的那条回复。另外第二个应该是nlogk :)

hankok 发表于 2018-6-20 11:04
粗略过了一下 楼上没错 是nlogn级别的

按pay排序(nlogn)：

@hankok
@FTD2014

感谢两位的回复，这个方法总的时间复杂度是(n - k)klogn 吧 klogn是找最小的k个数， n-k是次数， 如果用quick select 找最小的k个数是O（n）那总的复杂度是(n-k) * n. 如果有错烦请指正

martin5678 发表于 2018-6-20 12:35
@hankok
@FTD2014

你说的这个复杂度是对的，他们说的复杂度是有问题的

martin5678 发表于 2018-6-20 12:35
@hankok
@FTD2014

"找最小的k个数"这步并不是k*log(N)的，因为每次枚举只会新加入一个数，所以“最小的k个数”这个集合每次枚举最多更改一个元素，复杂度是log(N)的。外层枚举的复杂度O(N)，所以总的复杂度是Nlog(N)的

idatascience 发表于 2018-6-20 01:13
不好意思~我早上有点忙，回了一条就有急事出去了。~~~我刚才又想了想，觉得DP的n并不能直接从n-1推演（当 ...

哥们心胸宽广  令人佩服

分享一下最后一题我的思路.
依次扫描每一个员工 ： 1）比较当前员工的时薪和之前K个员工的最大时薪 2） 比较当前员工的时长和之前K个员工的最大时长， 会有以下四种情况
1) 时薪 < 最大时薪 && 时长 < 最大时长 ： 选择替换最大时薪或者最大时长
2 ）时薪 < 最大时薪 && 时长 >= 最大时长  :   查看是否替换最大时薪
3 ）时薪 >= 最大时薪 && 时长 < 最大时长  :   查看是否替换最大时长
4）时薪 >= 最大时薪 && 时长 》= 最大时长 ： 啥也不做。

需要维护两个heap，一个最大时薪， 一个最大时长，并且查找删除。总的复杂是o(nk)

决定去狗家的话，我在学工版有贴谷歌2018 fulltime群，可以去加下

what is the point for 易武巴 for java...

第五题和875是一个题吗

summerlismile 发表于 2018-6-25 02:23
第五题和875是一个题吗

875 ? 没搜到啊 ？是哪一题？