本文主要是介绍881. 救生艇,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目
给定数组 people
。people[i]
表示第 i
个人的体重,船的数量不限,每艘船可以承载的最大重量为 limit
。
每艘船最多可同时载两人,但条件是这些人的重量之和最多为 limit
。
返回承载所有人所需的最小船数。
示例 1:
- 输入:
people = [1,2]
,limit = 3
- 输出:
1
- 解释:1 艘船载 (1, 2)
示例 2:
- 输入:
people = [3,2,2,1]
,limit = 3
- 输出:
3
- 解释:3 艘船分别载 (1, 2), (2) 和 (3)
示例 3:
- 输入:
people = [3,5,3,4]
,limit = 5
- 输出:
4
- 解释:4 艘船分别载 (3), (3), (4), (5)
提示:
- 1 <= people.length <= 5 * 10^4
- 1 <= people[i] <= limit <= 3 * 10^4
代码
完整代码
#include <stdio.h>
#include <stdlib.h>int cmp(const void* a, const void* b)
{return (*(int*)b) - (*(int*)a);
}int numRescueBoats(int* people, int peopleSize, int limit) {int boatNum = 0;int firstManIndex = 0;int secondManIndex = peopleSize - 1;qsort(people, peopleSize, sizeof(int), cmp);for (; firstManIndex <= secondManIndex; firstManIndex++){if(people[firstManIndex] <= limit - people[secondManIndex]) // 能装下头尾两个人{secondManIndex--;}boatNum++;}return boatNum;
}
思路分析
题目的要求是找到能够把所有人运送到目的地所需的最小船数。每艘船最多能载两人,且两人的总重量不能超过 limit
。这是一个典型的贪心算法问题。
拆解分析
- 排序:首先将所有人的体重进行降序排序。这样可以确保每次尽可能的让较重的人和较轻的人配对,从而减少船的使用数量。
- 双指针:使用两个指针
firstManIndex
和secondManIndex
分别指向体重数组的头和尾。每次尝试将最重的人和最轻的人配对,如果他们的重量之和不超过limit
,则可以一起上船,移动尾指针;否则,最重的人单独上船。 - 计数船数:每次循环中,不论是配对成功还是失败,都需要增加船的数量。
复杂度分析
- 时间复杂度:排序的时间复杂度为
O(n log n)
,其中n
是people
数组的长度。双指针遍历数组的时间复杂度为O(n)
。因此,总的时间复杂度为O(n log n)
。 - 空间复杂度:排序的递归栈深度在最坏情况下为
O(n)
。双指针方法本身只使用了常数空间,因此总的空间复杂度为O(n)
。
在考虑递归栈的情况下,qsort
的空间复杂度取决于其递归深度。对于最坏情况(即每次选择的基准都导致最不平衡的分割),递归深度可以达到O(n)
,其中n
是数组的长度。然而,典型的实现通常使用一些优化,例如随机选择基准元素或三取样中值选择基准,这可以将平均情况下的递归深度降低到O(log n)
。
所以,qsort
在考虑递归栈的情况下,其空间复杂度如下:
最坏情况:O(n)
平均情况:O(log n)
因此,在我们的分析中,需要考虑最坏情况下的 O(n)
递归栈空间复杂度。
结果
这篇关于881. 救生艇的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!