力扣493.翻转对
力扣493.翻转对
-
贪心 + 树状数组
- 将2*v和v一起加入st集合离散化
- 最小的数编号越小
- 之后在把nums[i]加入树状数组时，求编号低的即可
-
为什么要把2*v也一起离散化？
- 因为我们通过比较编号来比较数字大小
- 如果2*v不离散化，它就没有对应编号，无法比较
-
const int N = 100010;int tr[N],n,limit;class Solution {public:int reversePairs(vector<int>& nums) {n = nums.size();set<long long> st;for(int v:nums){st.insert(v);st.insert((long long)2*v);}int i=1;unordered_map<long long,int> mp;for(auto s:st)mp[s] = i++;memset(tr,0,sizeof tr);int count=0;limit = st.size();for(int i=n-1;i>=0;i--){int r = mp[nums[i]];count += sum(r-1);add(mp[(long long)nums[i]*2],1);}return count;}int lowbit(int x){return x & -x;}void add(int x,int c){for(int i=x;i<=limit;i+=lowbit(i)) tr[i] += c;}int sum(int x){int res=0;for(int i=x;i;i-=lowbit(i)) res += tr[i];return res;}};