【Leetcode】493. Reverse Pairs

题目地址：

https://leetcode.com/problems/reverse-pairs/

给定一个长$n$的数组$A$，求$|\{(i,j):i<j\wedge A[i]>2A[j]\}|$。

可以用树状数组。先将$A$连同$2A$一起做保序离散化（用哈希表），接着可以用经典求法。遍历$A$，对于$A[i]$，我们求一下$A[0:i-1]$里满足小于等于$2A[i]$的数有多少个，可以在树状数组里求前缀和，如果有$t$个，则大于$2A[i]$的就有$i-t$个；然后再将$A[i]$离散化之后，将这个位置的数加$1$即可。代码如下：

class Solution {
    
 public:
  #define lowbit(x) (x & -x)
  vector<int> tr;
  int n;

  void add(int k, int x) {
    
    for (; k <= n; k += lowbit(k)) tr[k] += x;
  }

  int sum(int k) {
    
    int res = 0;
    for (; k; k -= lowbit(k)) res += tr[k];
    return res;
  }

  int reversePairs(vector<int>& A) {
    
    vector<long> tmp(A.begin(), A.end());
    for (auto &x : A) tmp.push_back(2L * x);
    sort(tmp.begin(), tmp.end());
    n = unique(tmp.begin(), tmp.end()) - tmp.begin();
    unordered_map<long, int> mp;
    for (int i = 0; i < n; i++) mp[tmp[i]] = i + 1;
    tr = vector<int>(n + 1);

    int res = 0;
    for (int i = 0, x; i < A.size(); i++) {
    
      x = A[i];
      res += i - sum(mp[x * 2L]);
      add(mp[x], 1);
    }

    return res;
  }
};

时间复杂度$O(n\log n)$，空间$O(n)$。

Java：

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Solution {
    
    
    int[] tr;
    int n;
    
    int lowbit(int x) {
    
        return x & -x;
    }
    
    void add(int k, int x) {
    
        for (; k <= n; k += lowbit(k)) {
    
            tr[k] += x;
        }
    }
    
    int sum(int k) {
    
        int res = 0;
        for (; k > 0; k -= lowbit(k)) {
    
            res += tr[k];
        }
        return res;
    }
    
    public int reversePairs(int[] A) {
    
        long[] tmp = new long[A.length << 1];
        for (int i = 0; i < A.length; i++) {
    
            tmp[2 * i] = A[i];
            tmp[2 * i + 1] = A[i] * 2L;
        }
        
        Arrays.sort(tmp);
        int m = 0;
        for (int i = 0; i < tmp.length; i++) {
    
            if (m == 0 || tmp[i] > tmp[m - 1]) {
    
                tmp[m++] = tmp[i];
            }
        }
        
        Map<Long, Integer> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
    
            map.put(tmp[i], i + 1);
        }
        
        n = m;
        tr = new int[m + 1];
        
        int res = 0;
        for (int i = 0, x; i < A.length; i++) {
    
            x = A[i];
            res += i - sum(map.get(x * 2L));
            add(map.get((long) x), 1);
        }
        
        return res;
    }
}

时空复杂度一样。