881. 救生艇 - Boats To Save People
[双指针] [桶排序]
第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
Example:
输入：people = [1,2], limit = 3
输出：1
解释：1 艘船载 (1, 2)
输入：people = [3,2,2,1], limit = 3
输出：3
解释：3 艘船分别载 (1, 2), (2) 和 (3)
solution
My solution >> 54ms [双指针 + 贪心算法 ]
如果最重的人可以与最轻的人共用一艘船，那么就这样安排。
否则，最重的人无法与任何人配对，那么他们将自己独自乘一艘船。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
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;
}
}
|
复杂度分析 O(N)
Other Solution >> 16ms [桶排序]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
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)
Notes
桶排序
桶排序的平均时间复杂度为线性的O(N+C)，其中C=N*(logN-logM)。
如果相对于同样的N，桶数量M越大，其效率越高，最好的时间复杂度达到O(N)。
桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。
此外，桶排序是稳定的。