|
亲!马上注册或者登录会查看更多内容!
您需要 登录 才可以下载或查看,没有帐号?立即注册
x
题目数据量不大,也提示了sort+greedy,可以优化的地方在于(1)对于a中任意一个数,如果在b中找不到可以配对的,则可以直接返回false
(2)对于a中任意一个数,如果b[0]就可以配对,则可以直接返回true,这是因为剩下的a[]和b[]都不比当前的pair小
- #include <set>
- using std::set;
- class Solution {
- public:
- bool canPair(vector<int> &a, vector<int> &b, int k) {
- sort(a.begin(), a.end());
- sort(b.begin(), b.end());
- for(int x : a){
- auto iter = b.begin();
- for(; iter != b.end(); ++iter){
- if(x + *iter >= k) break;
- }
- if(iter == b.end()) return false;
- if(iter == b.begin()) break;
- b.erase(iter);
- }
- return true;
- }
- };
复制代码 上述算法空间复杂度是O(1)的,时间复杂度最坏是O(N^2),可以看到内层循环实际是在sorted的b中寻找可以和a【i】配对的项,即lower_bound,自然的想到用set,且set对iterator的erase是O(1)的,我们便可以用O(N)的额外空间将时间复杂度降至O(NlgN):
- #include <set>
- using std::set;
-
- class Solution {
- public:
- bool canPair(vector<int> &a, vector<int> &b, int k) {
- sort(a.begin(), a.end());
- set<int> ss(b.begin(), b.end());
- for(int x : a){
- auto iter = ss.lower_bound(k-x);
- if(iter == ss.end()) return false;
- if(iter == ss.begin()) break;
- ss.erase(iter);
- }
- return true;
- }
- };
复制代码
|
评分
-
查看全部评分
|