2: Make Pairs

uuuouou

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

1. #include <set>
   
2. using std::set;
   
3. 
   
4. class Solution {
   
5. public:
   
6.         bool canPair(vector<int> &a, vector<int> &b, int k) {
   
7.                 sort(a.begin(), a.end());
   
8.                 sort(b.begin(), b.end());
   
9.                 for(int x : a){
   
10.                         auto iter = b.begin();
    
11.                         for(; iter != b.end(); ++iter){
    
12.                                 if(x + *iter >= k) break;
    
13.                         }
    
14.                         if(iter == b.end()) return false;
    
15.                         if(iter == b.begin()) break;
    
16.                         b.erase(iter);
    
17.                 }
    
18.                 return true;
    
19.         }
    
20. };

复制代码

上述算法空间复杂度是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. 
   
4. class Solution {
   
5. public:
   
6.     bool canPair(vector<int> &a, vector<int> &b, int k) {
   
7.         sort(a.begin(), a.end());
   
8.         set<int> ss(b.begin(), b.end());
   
9.         for(int x : a){
   
10.             auto iter = ss.lower_bound(k-x);
    
11.             if(iter == ss.end()) return false;
    
12.             if(iter == ss.begin()) break;
    
13.             ss.erase(iter);
    
14.         }
    
15.         return true;
    
16.     }
    
17. };

复制代码

刘畅

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. };

复制代码

uuuouou

刘畅 发表于 10-6-2015 11:36 PM

感谢分享~~~