本文最后更新于 393 天前,其中的信息可能已经有所发展或是发生改变。
题目描述:
给你一个整数数组 ranks
,表示一些机械工的 能力值 。ranks[i]
是第 i
位机械工的能力值。能力值为 r
的机械工可以在 r * n^2
分钟内修好 n
辆车。
同时给你一个整数 cars
,表示总共需要修理的汽车数目。
请你返回修理所有汽车 最少 需要多少时间。
**注意:**所有机械工可以同时修理汽车。
示例 1:
输入:ranks = [4,2,3,1], cars = 10
输出:16
解释:
- 第一位机械工修 2 辆车,需要 4 * 2 * 2 = 16 分钟。
- 第二位机械工修 2 辆车,需要 2 * 2 * 2 = 8 分钟。
- 第三位机械工修 2 辆车,需要 3 * 2 * 2 = 12 分钟。
- 第四位机械工修 4 辆车,需要 1 * 4 * 4 = 16 分钟。
16 分钟是修理完所有车需要的最少时间。
示例 2:
输入:ranks = [5,1,8], cars = 6
输出:16
解释:
- 第一位机械工修 1 辆车,需要 5 * 1 * 1 = 5 分钟。
- 第二位机械工修 4 辆车,需要 1 * 4 * 4 = 16 分钟。
- 第三位机械工修 1 辆车,需要 8 * 1 * 1 = 8 分钟。
16 分钟时修理完所有车需要的最少时间。
提示:
1 <= ranks.length <= 105
1 <= ranks[i] <= 100
1 <= cars <= 106
解法一:二分查找
算法思路:
根据题目要求要查找最少时间,如果解在值域范围内存在单调性,就能够使用二分查找:
- 假设 t 分钟内可以将所有汽车都修理完,那么大于等于 t 分钟内都可以将所有汽车修理完。
- 假设 t 分钟内不能够将所有汽车都修理完,那么小于等于 t 分钟内也不能够将所有汽车修理完。
所以存在单调性。
显然任意一人修完所有车的时间都要大于最少的时间,所以我们定义二分查找的左右边界分别为 left = 0,right = ranks[ 0 ] * cars * cars。依次枚举修车时间 mid,每个机械工人可以休息的汽车数量为 sqrt( mid / rank ),
如果修理的汽车数目大于等于 cars,说明修车时间 mid 可行,那么将右边界缩小至 mid,否则将左边界增大至 mid + 1.
最终返回左边界即可。
代码实现:
class Solution {
public long repairCars(int[] ranks, int cars) {
long left = 0, right = 1L * ranks[0] * cars * cars;
while(left < right){
long mid = (left + right) >> 1;
long cnt = 0;
for(int rank : ranks){
cnt += Math.sqrt(mid / rank);
}
if(cnt >= cars){
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
复杂度分析:
时间复杂度: O( n * log( M )),其中 n 为机械工的数量,M 为二分查找的上界。
空间复杂度: O( 1 )