[双指针] [桶排序]
第 i 个人的体重为 people[i],每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
输入:people = [1,2], limit = 3
输出:1
解释:1 艘船载 (1, 2)
输入:people = [3,2,2,1], limit = 3
输出:3
解释:3 艘船分别载 (1, 2), (2) 和 (3)
如果最重的人可以与最轻的人共用一艘船,那么就这样安排。
否则,最重的人无法与任何人配对,那么他们将自己独自乘一艘船。
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int answer = 0;
int i = 0, j = people.length - 1;
while(i <= j){
if(people[i] + people[j] <= limit) i++;
j--;
answer++;
}
return answer;
}
}
class Solution {
//对于Limite很小的情况用桶排序
public int numRescueBoats(int[] people, int limit) {
int[] busket = new int[limit + 1];
for(int i = 0; i < people.length; i++)
busket[people[i]] += 1;
int count = busket[limit]; // 先让所有只能一个人坐船的人离开
int start = 1;
int end = limit - 1;
//1号桶到倒数第二个桶
while(start <= end){
if(busket[start] <= 0){
start++;
continue;
}
if(busket[end] <= 0){
end--;
continue;
}
if(start + end == limit){
busket[start]--;
busket[end]--;
count++;
continue;
}
if(start + end > limit){
busket[end]--;
count++;
continue;
}
if(start + end < limit){
busket[end]--;
busket[start]--;
count++;
continue;
}
}
return count;
}
}
桶排序
桶排序的平均时间复杂度为线性的O(N+C),其中C=N*(logN-logM)。
如果相对于同样的N,桶数量M越大,其效率越高,最好的时间复杂度达到O(N)。
桶排序的空间复杂度为O(N+M),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。
此外,桶排序是稳定的。