1. 救生艇 - Boats To Save People

881. 救生艇 - Boats To Save People

[双指针] [桶排序]

Problem Link

第 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
14
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
42
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),如果输入数据非常庞大,而桶的数量也非常多,则空间代价无疑是昂贵的。

此外,桶排序是稳定的。

updatedupdated2021-03-052021-03-05