狗家电面

wofaint 发表于 2018-11-11 05:28
这道题有两种解法：1. 是二分答案，时间复杂度是 O(P*log(W))， P是人数，W是工资范围（max_wage - budget  ...

是这样的

wofaint 发表于 2018-11-11 05:28
这道题有两种解法：1. 是二分答案，时间复杂度是 O(P*log(W))， P是人数，W是工资范围（max_wage - budget  ...

至矣尽矣 无可加矣

[quote]frankchang0311 发表于 2018-11-10 14:16
不知道这样对吗，O(n)

1.     public static long findK(int[] salary, int budget)  ...[/quote]
3. 你的代码有个小问题，就是不能处理连salary[0]都需要降低的情况，比如{100, 200, 300}, 100
   
4. 改成这样你看怎么样：
   
5. [code]public static int findK(int[] salary, int budget) {
   
6.     int n = salary.length;
   
7.     int sum = 0;
   
8.     Arrays.sort(salary);
   
9.     for (int i = 0; i < n; i++) {
   
10.         int lowerbound = budget / (n - i);  // i~n-1的工资如果全降的话，需要降到这么多
    
11.         if (salary[i] < lowerbound) {       // 如果salary[i]低于这个需要降到的值，
    
12.             budget -= salary[i];            // 那么salary[i]一定不需要降，跳过即可
    
13.         }
    
14.         else {
    
15.             return lowerbound;              // 否则剩下所有人工资降到lowerbound即可
    
16.         }
    
17.     }
    
18.     return 0;
    
19. }

复制代码

补充内容 (2018-11-11 07:12):
全乱了……引用中包含了别人的代码标签，正文中又有代码标签时好像就会这样？

stellari 发表于 2018-11-11 07:06
你的代码有个小问题，就是不能处理连salary[0]都需要降低的情况，比如{100, 200, 300}, 100
改成这样你 ...

我觉得应该是对的

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

1. 
   
2. public int findK(int[] salary, int budget) {
   
3.         int n = salary.length;
   
4.         int base = 0;
   
5.         while(budget/n != base) {
   
6.             base = budget / n;
   
7.             int pointer = 0, count = n;
   
8.             for(int i = 0; i < n; i++) {
   
9.                 if(salary[i] <= base) {
   
10.                     budget -= salary[i];
    
11.                     count--;
    
12.                 }
    
13.                 else
    
14.                     salary[pointer++] = salary[i];
    
15.             }
    
16.             n = count;
    
17.         }
    
18.     return base;
    
19. }
    

复制代码

stellari 发表于 2018-11-13 11:25
这样不行，因为小于等于base的数确实一定不需要降低，但是大于base的数并不一定需要降低。所以仅根据base ...

噢！get！我就说感觉如果我这样考虑这题就太 easy 了没什么考点了，原来问题在这里！