救生艇
第 i 个人的体重为 people[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)
思路就是贪心:
就是先让一个人上船,看看省的位置还够不够另一个人来,尽可能把位置坐满;比如体重为 a 的 上船就看看有没有 limit - a 体重的人跟他一起,没有找 limit - a - 1的,等等等。
自己做的,刚开始想的数据不大,可以用空间换时间,能AC!
class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int book[30005]; int ans = people.size(); memset(book,0,sizeof(book)); for(int i = 0; i < people.size(); i++){ book[people[i]]++; } for(int i = 0; i < people.size(); i++){ if(book[people[i]] <= 0)continue; int x = limit - people[i]; book[people[i]]--; while(x > 0){ if(book[x] > 0){ book[x]--; ans--; break; } x--; } } return ans; } };
还有更简便的,现将原数组排序,然后两头搜索,由于是要排序,所以时间复杂度要 nlogn;
class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int ans = 0; int l = 0, r = people.size() - 1; sort(people.begin(),people.end()); while(l <= r){ if(people[l] + people[r] <= limit)l++; r--; ans++; } return ans; } };
这看着是真迷糊,可能大家写的时空复杂度都一样;