You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

881. 救生艇 - Boats To Save People

. 2 min read

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 [双指针 + 贪心算法 ]

如果最重的人可以与最轻的人共用一艘船,那么就这样安排。

否则,最重的人无法与任何人配对,那么他们将自己独自乘一艘船。

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 [桶排序]

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

此外,桶排序是稳定的。