找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1000|回复: 3
收起左侧

[资源分享] 2: Make Pairs

[复制链接]

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
发表于 10-3-2015 12:06 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
题目数据量不大,也提示了sort+greedy,可以优化的地方在于(1)对于a中任意一个数,如果在b中找不到可以配对的,则可以直接返回false
(2)对于a中任意一个数,如果b[0]就可以配对,则可以直接返回true,这是因为剩下的a[]和b[]都不比当前的pair小

  1. #include <set>
  2. using std::set;

  3. class Solution {
  4. public:
  5.         bool canPair(vector<int> &a, vector<int> &b, int k) {
  6.                 sort(a.begin(), a.end());
  7.                 sort(b.begin(), b.end());
  8.                 for(int x : a){
  9.                         auto iter = b.begin();
  10.                         for(; iter != b.end(); ++iter){
  11.                                 if(x + *iter >= k) break;
  12.                         }
  13.                         if(iter == b.end()) return false;
  14.                         if(iter == b.begin()) break;
  15.                         b.erase(iter);
  16.                 }
  17.                 return true;
  18.         }
  19. };
复制代码
上述算法空间复杂度是O(1)的,时间复杂度最坏是O(N^2),可以看到内层循环实际是在sorted的b中寻找可以和a【i】配对的项,即lower_bound,自然的想到用set,且set对iterator的erase是O(1)的,我们便可以用O(N)的额外空间将时间复杂度降至O(NlgN):

  1. #include <set>
  2. using std::set;

  3. class Solution {
  4. public:
  5.     bool canPair(vector<int> &a, vector<int> &b, int k) {
  6.         sort(a.begin(), a.end());
  7.         set<int> ss(b.begin(), b.end());
  8.         for(int x : a){
  9.             auto iter = ss.lower_bound(k-x);
  10.             if(iter == ss.end()) return false;
  11.             if(iter == ss.begin()) break;
  12.             ss.erase(iter);
  13.         }
  14.         return true;
  15.     }
  16. };
复制代码


评分

参与人数 1金钱 +6 收起 理由
Sophia + 6 很给力!

查看全部评分

0

主题

0

精华

4

积分

新米人

Rank: 1

积分
4
发表于 10-6-2015 11:36 PM | 显示全部楼层
  1. class Solution {
  2. public:
  3.         bool canPair(vector<int> &a, vector<int> &b, int k) {
  4.                 sort(a.begin(), a.end());
  5.                 sort(b.begin(), b.end(), greater<int>());
  6.                 for (int i(0); i < a.size(); ++i)
  7.                         if (a【i】 + b【i】 < k)
  8.                                 return false;
  9.                 return true;
  10.         }
  11. };
复制代码

评分

参与人数 1金钱 +3 收起 理由
Sophia + 3 赞一个!

查看全部评分

回复 支持 反对

使用道具 举报

19

主题

2

精华

83

积分

资深会员

Rank: 2

积分
83
 楼主| 发表于 10-7-2015 12:31 AM | 显示全部楼层
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表