一亩三分地

 找回密码 注册账号

扫描二维码登录本站


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
楼主: 宇宙小清新
收起左侧

狗家电面

[复制链接] |试试Instant~
我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (30)
 
 
6% (2)    👎
frankchang0311 发表于 2018/11/10 14:16:54
不知道这样对吗,O(n)
[mw_shl_code=java,true]    public static long findK(int[] salary, int budget) {
     ...

sort就已经是nlogn了吧
回复 微信

使用道具 举报

我的人缘0
frankchang0311 2018-11-10 14:36:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
tai扯了 发表于 2018-11-10 14:30
sort就已经是nlogn了吧

对,如果排了序是O(n), 没有的话O(nlogn)
回复

使用道具 举报

我的人缘0
foryousee 2018-11-10 14:55:51 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   90% (110)
 
 
9% (11)    👎
tai扯了 发表于 2018-11-10 14:29
所以这个是未排序的nlogn解法

是的,字数
回复

使用道具 举报

我的人缘0
当横压一代 2018-11-10 16:25:05 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   97% (121)
 
 
2% (3)    👎
frankchang0311 发表于 2018-11-10 14:16
不知道这样对吗,O(n)
[mw_shl_code=java,true]    public static long findK(int[] salary, int budget)  ...

这个666字数字数

补充内容 (2018-11-10 16:41):
要考虑一下这种情况:[100, 200, 300, 400], budget = 40。
回复

使用道具 举报

我的人缘0
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   94% (35)
 
 
5% (2)    👎
我觉得是不是可以不排序,拿楼主那个例子来说,首先800/4=200,然后去数组里找比200小的元素,统计总共小的金额:100,然后这一百就可以分给比200大的人,一人50,于是就是250。不知道这样对不对?
回复

使用道具 举报

我的人缘0
郁小南 2018-11-11 02:06:06 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (193)
 
 
3% (7)    👎
foryousee 发表于 2018-11-10 13:40
麻烦问一下stack怎么做?实在想不出来。binary search其实跟排不排序没关系。每一次binary search的cost ...

cur (average budget) = budget / length, 用Stack存比当前average budget高的数字,如果遇到比当前平均预算要低的,cur = cur + (cur - number)/(remaining people); remaining people -= 1, 再依次pop stack顶部比cur低的数字并做相同操作。
测试了几个感觉应该是对的
回复

使用道具 举报

我的人缘0
郁小南 2018-11-11 02:16:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (193)
 
 
3% (7)    👎
foryousee 发表于 2018-11-10 13:40
麻烦问一下stack怎么做?实在想不出来。binary search其实跟排不排序没关系。每一次binary search的cost ...

啊发现Stack不行……就算要用这样的方法也得用个Heap_(:з」∠)_
回复

使用道具 举报

我的人缘0
lzhong 2018-11-11 03:53:13 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
能不能用两个binary search。  第一个binary search 跟前面童鞋们说的一样。
start 是当前budget 的average pay. end 是max salary.  

然后每次binary search 的时候要判断当前的 mid  导致的总的salary 是大于budget
的还是小于 budget.   这一步可以再用一次binary search。

具体做法是 把salary sort 了。 然后对于sorted salary 求一个prefix sum. 对于每一个
mid, 找以第一个比mid 小的数。 比如index 是 i。  那么当前的total salary 就是
prefix[i+1] + (n-1-i)* mid
因为凡是大于等于 mid 的salary 都会是 mid.

用stack 的话感觉也可行, 可以存比当前稍高工资低的工资。 比如说[100, 200,300]
budget 是 300. 我们知道200 过高。 stack 就只存100.




回复

使用道具 举报

我的人缘0
坨坨 2018-11-11 05:07:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   81% (45)
 
 
18% (10)    👎
frankchang0311 发表于 2018-11-10 14:16
不知道这样对吗,O(n)
[mw_shl_code=java,true]    public static long findK(int[] salary, int budget)  ...

"sums"数组貌似不需要?
回复

使用道具 举报

我的人缘0
wofaint 2018-11-11 05:28:29 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (5)
 
 
0% (0)    👎
这道题有两种解法:1. 是二分答案,时间复杂度是 O(P*log(W)), P是人数,W是工资范围(max_wage - budget / P),不用对工资数组排序( foryousee 的解法);2. 是先对工资数组排序,再遍历(frankchang0311 的解法),时间复杂度是O(P) 如果工资数组已排序,否则是 O(P*log(P)) 因为要先排序。两种解法的空间复杂度都是O(1).
两种解法各有优劣(看 P 大还是 W 大)。

评分

参与人数 1大米 +3 收起 理由
hazai + 3 给你点个赞!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版||一亩三分地

GMT+8, 2019-8-21 03:29

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表