一、题目
二、解题思路
题目要求每艘船最多能载两人,为了使船的使用数量最少,我们应尽可能地让每艘船载两人。解决这个问题的策略是首先对数组进行排序,然后优先考虑体重最重的个体。
具体步骤如下:
1. **排序**:将数组中的体重按从小到大的顺序排列。
2. **配对**:从体重最重的个体开始,检查其是否能与体重最轻的个体同乘一船。如果能,则让他们同乘;如果不能,则体重最重的个体只能单独乘船。
3. **迭代**:继续上述过程,依次考虑体重次重的个体,直到所有人都被分配到船上。
通过这种策略,我们可以最大限度地利用每艘船的载人能力,从而减少船的总使用数量。
三、代码实现
#include <iostream>
#include <vector>
#include <algorithm>int numRescueBoats(std::vector<int>& people, int limit) {// 先对数组进行排序(人发重量按照从小到大的顺序排序)std::sort(people.begin(), people.end());// 统计船的个数int count = 0;// 从小到大排序,左边的是最小的,右边的是最大的int left = 0;int right = people.size() - 1;while (left <= right) {// 如果体重最大的和体重最小的可以单独乘坐// 一条船,就让他们同乘一条船if (people[right] + people[left] <= limit)left++;// 体重最大的每次都要减1right--;// 使用船的数量count++;}return count;
}int main() {std::vector<int> people = {3, 2, 2, 1};int limit = 3;int result = numRescueBoats(people, limit);std::cout << "Number of boats needed: " << result << std::endl;return 0;
}
时间复杂度
-
排序:使用
std::sort
函数对数组进行排序。在C++中,std::sort
通常使用的是快速排序(QuickSort)、堆排序(HeapSort)或插入排序(InsertionSort)的混合算法,其平均时间复杂度为 O(nlogn),其中 n 是数组的长度。 -
双指针遍历:使用双指针从两端向中间遍历数组。这个过程的时间复杂度是 O(n),因为每个元素最多被访问一次。
综合起来,整个算法的时间复杂度是 O(nlogn),主要由排序部分决定。
空间复杂度
-
排序:
std::sort
的空间复杂度取决于其实现方式。通常情况下,快速排序的空间复杂度是 O(logn),而堆排序的空间复杂度是 O(1)。C++标准库中的std::sort
通常会使用一些额外的空间,但不会超过 O(logn)。 -
双指针遍历:双指针遍历本身不需要额外的空间,空间复杂度是 O(1)。
综合起来,整个算法的空间复杂度是 O(logn),主要由排序部分决定。