在两个数组中计数反转

Question

数组中的反转是一对索引（i，j），使得a[i]

给定2个数组A和B，我们必须返回这样的对的数目，这样A[i]

例子：

设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

Answer 1

有一个想法：
1。合并两个原始数组，使具有相同索引的每对元素彼此相邻。（您需要放置元素，使较低的元素位于较高的元素之前）
3。计算结果数组中的反转数，如下所述。

编辑：对不起，我误解了这个问题。如果只需要从a（I）到b（j）的反转，那么可以使用另一个字段arraytype（a或b）标记每个元素。然后，在合并排序时，只有当反转从arraytype a到b时，才能增加计数。

Answer 2

您可以使用合并排序思想找到两个数组之间的倒置！

假设你有两个大小相同的数组，让我们称它们为A、B，如果我们分别表示A的前半部分、A1和A的后半部分、A2和B1和B2，那么我们可以得出结论：

1. A1和B1之间的反转
2. A2和B2之间的反转
3. A1和B2之间的反转

递归调用函数可以支持前两个元素，但是如何计算第三个元素呢？

我们的想法是从左到右遍历A1和B2，其中B1中的元素大于A1中的元素，然后A1中尚未访问的元素应相加为反转数，最后我们只将A1和A2排序为A，将B1和B2排序为B

下面是python中的代码：

def find_inv(A, B):

if len(A) <= 1:
    return 0
mid = len(A) // 2
A1 = A[:mid]
A2 = A[mid:]
B1 = B[:mid]
B2 = B[mid:]

if len(A1) >= 1 and len(B2) >= 1:
    ans = find_inv(A1, B1) + find_inv(A2, B2)
else:
    A.sort()
    B.sort()
    ans = 0
len_A = len(A1)
index_A = 0
len_B = len(B2)
index_B = 0

for k in range(len_A + len_B):

    if A1[index_A] <= B2[index_B]:

        index_A += 1
        if index_A == len_A:
            merge(A1, A2, A)
            merge(B1, B2, B)

            return ans
    else:
        index_B += 1
        ans += (len_A - index_A)

        if index_B == len_B:
            merge(A1, A2, A)
            merge(B1, B2, B)
            return ans

def merge(A1, A2, dest):
i = 0
j = 0


while i < len(A1) and j < len(A2):
    if A1[i] < A2[j]:
        dest[i+j] = A1[i]
        i += 1
    else:
        dest[i+j] = A2[j]
        j += 1
while i < len(A1):
        dest[i+j] = A1[i]
        i += 1

while j < len(A2):
        dest[i+j] = A2[j]
        j += 1

Answer 3

我在过去写过关于如何使用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;
}

基本上，我们从右到左遍历数组，维护一个表示后缀中已经看到的a值的数据结构。对于每个元素b[i]，我们将数据结构中元素x的数量与x一起添加到最终结果中

数组值用于将值的范围压缩为1。。2n因为芬威克树在范围大小上呈线性空间。我们可以通过选择一个功能更全面的数据结构来避免这一步，比如平衡的bjnary搜索树，并增加子树的大小。

复杂度为O（n log n），常数因子很低。