计算两个数组中的反转

Question

数组中的反转是一对索引(i,j),使得a [i]> a [j]和i <j.

给定2个阵列A和B,我们必须返回这样的对的数量,使得a [i]> b [j]和i <j.

示例:

设n = 3,A [] = [5,6,7],B [] = [1,2,3]则答案为3. 3对为(5,2),(5,3)和(6 ,3).

我的代码:

#include <stdio.h>
#include <stdlib.h>
int main()
{
    int len;
    scanf("%d",&len);
    int a[len];
    int b[len];
    for(int i = 0; i < len; i++)
       scanf("%d",&a[i]);
    for(int i = 0; i < len; i++)
       scanf("%d",&b[i]);
    int count = 0;
    for (int i = 0;i < len; i++)
    {
        for(int j = i+1; j < len; j++)
        {
             if(a[i] > b[j])
             {
                 count++;
             }
         }
     }
     printf("%d",count);
}

但这是O(N ^ 2)解决方案.我需要一个更好的解决方案,因为N <= 200000.I我知道我们可以在O(N*Log N)时间内对同一个数组中的反演进行计数.但是如何对两个不同的数据进行计算数组？

Answer 1

我过去曾写过如何使用Fenwick树计算反转,这是一种非常有效的二叉树类型,可以让您计算序列上的前缀聚合.

以下是针对您的方案的特殊修改:

long long inversions(const vector<int>& a, const vector<int>& b) {
  int n = a.size();
  vector<int> values(a);
  for (int x: b) values.push_back(x);
  sort(begin(values), end(values));
  vector<int> counts(2*n + 1);
  long long res = 0;
  for (int i = n - 1; i >= 0; --i) {
    // compute sum of prefix 1..rank(a[i]) - 1
    for (int v = lower_bound(begin(values), end(values), a[i]) - begin(values);
         v; 
         v -= v & -v)
      res += counts[v];
    //add 1 to point rank(b[i])
    for (int v = lower_bound(begin(values), end(values), b[i]) - begin(values) + 1;
         v <= 2*n;
         v += v & -v)
      counts[v]++;
  }
  return res;
}

基本上我们从右到左遍历数组,维护一个数据结构,代表我们在后缀中看到的值.对于每个元素b [i],我们在数据结构中添加元素x的数量,其中x <= b [i] - 1.然后我们将[i]添加到数据结构中.

该数组values用于将值的范围压缩为1..2n,因为Fenwick树在范围大小中采用线性空间.我们可以通过选择更全面的数据结构来避免这一步骤,例如具有子树大小增强的平衡bjnary搜索树.

复杂度为O(n log n),常数因子非常低.