[二分查找双指针]LeetCode881: 救生艇

救生艇

作者推荐

[二分查找]LeetCode2040:两个有序数组的第 K 小乘积

本文涉及的基础知识点

二分查找算法合集

题目

给定数组 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⁴
1 <= people[i] <= limit <= 3 * 10⁴

二分查找

分析法

最少船数=人数-最多搭伙坐船数。如果能搭伙m组人，则还需要计算能否搭伙更多的船，左闭右开空间。

代码

class Solution {
public:
int numRescueBoats(vector& people, int limit) {
sort(people.begin(), people.end());
int left = 0, right = people.size() / 2 + 1;//左闭右开空间
while (right - left > 1)
{
const int mid = left + (right - left) / 2;
if (Is(people, mid, limit))
{
left = mid;
}
else
{
right = mid;
}
}
return people.size() - left;
}
bool Is(const vector& people, int num, int limit)
{
for (int i = 0; i < num; i++)
{
if (people[i] + people[num * 2 - 1 - i] > limit)
{
return false;
}
}
return true;
}
};

测试用例

void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
assert(v1[i] == v2[i]);
}
}

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

int main()
{
vector people;
int limit, res;
{
people = { 3,2,3,2,2 };
limit = 6;
Solution slu;
auto res = slu.numRescueBoats(people, limit);
Assert(3, res);
}
{
people = { 1, 2 };
limit = 3;
Solution slu;
auto res = slu.numRescueBoats(people, limit);
Assert(1, res);
}
{
people = { 3,2,2,1 };
limit = 3;
Solution slu;
auto res = slu.numRescueBoats(people, limit);
Assert(3, res);
}
{
people = { 3,5,3,4 };
limit = 5;
Solution slu;
auto res = slu.numRescueBoats(people, limit);
Assert(4, res);
}

//CConsole::Out(res);

}

双指针

分析

排序后，left和right合伙坐船，left <= right时结束。如果有多人能和left合伙，取体重最重的。随着left增加，right减少。

代码

class Solution {
public:
int numRescueBoats(vector& people, int limit) {
sort(people.begin(), people.end());
int left = 0,right = people.size()-1;
while (left < right )
{
while ((right > left) && (people[left] + people[right] > limit))
{
right–;
}
if (right > left)
{
left++;
right–;
}
}
return people.size() - left;
}
};