首页 > 代码库 > 【leetcode】493. Reverse Pairs
【leetcode】493. Reverse Pairs
好吧这其实是一次小比赛,在回上海前的周末。好久没打比赛,简单题也只是AK了而已,还TM错了一次。最后45名57分钟加一次罚时,第一名18分钟,好吧。也行了对于业余组选手。
错在没考虑到乘2会超max_int。
程序没了,也没心情找了。孤单的情人节。
貌似有两个人被发现作弊了我变成了43名,还找到了程序,也算一点小小的安慰吧。
class Solution { public: int reversePairs(vector<int>& aa) { vector<long long> a = vector<long long>(aa.size(),0); for (int i = 0;i<aa.size();i++) a[i] = aa[i]; auto a2 = a; for (auto& x : a2) x *= 2; vector<long long> all = a; for (auto x : a2) all.push_back(x); sort(all.begin(),all.end()); all.resize(distance(all.begin(),unique(all.begin(),all.end()))); map<long long,int> m; for (int i = 0;i<all.size();i++) m[all[i]] = i; for (auto& x : a) x = m[x]; for (auto& x : a2) x = m[x]; int N = all.size(); tree = vector<int>(N * 10,0); int ret = 0; for (int i = a2.size() - 1;i>= 1;i--) { insert(0,0,N-1,a2[i]); auto tmp = find(0,0,N-1,0,a[i-1] - 1); //cout << tmp << endl; ret += tmp; } return ret; } private: vector<int> tree; void insert(int p,int l,int r,int x) { if (l <= x && x <= r) tree[p]++; if (l == r) return; int m = (l+r) / 2; if (x <= m) insert(p*2+1,l,m,x); else insert(p*2+2,m+1,r,x); } int find(int p,int l,int r,int tl,int tr) { if (tl > tr) return 0; if (l == tl && r == tr) return tree[p]; int m = (l + r)/2; if (tr <= m) return find(p*2+1,l,m,tl,tr); if (tl >= m+1) return find(p*2+2,m+1,r,tl,tr); return find(p*2+1,l,m,tl,m) + find(p*2+2,m+1,r,m+1,tr); } };
【leetcode】493. Reverse Pairs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。