使用 1、2、...、n 的三个排列进行计数合并排序，在 O(n log n) 中工作

问题描述 投票：0回答：3

我正在寻找一种在 O(n log n) 中运行的算法，可能基于合并排序和计数。这将给出 3 个字符串（字符串 1、2、3、...、n 的排列）中此类对的数量，其中一对中的一个数字跟在每个字符串中的另一对数字后面（无限连续） 3 个字符串，顺序相同。

例如，对于字符串：

1 2 4 3

4 1 2 3

4 3 1 2

只有两对（1 和 2、4 和 3），所以算法应该返回 2，因为在这 3 个字符串中，只有这些对以相同的顺序出现

例如，对于字符串：

1 2 3 4 5

4 2 1 5 3

3 4 5 2 1

它应该返回一个，因为只有一对 4 和 5

O(n^2)复杂度很容易解决这个问题。但我正在寻找更快的解决方案。我试图根据对给定列表进行排序所需的更改次数来找到一些依赖项，但结果很差

我在下面给出我的 O(n^2) 解决方案：

// O(n ^ 2)

#include <iostream>
#include <vector>

using namespace std;

int main()
{
        int n;
        cin >> n;
        
        vector<int> ax(n);
        for (int i = 0; i < n; i++)
        {
            int tmp;
            cin >> tmp;
            tmp--;
            ax[tmp] = i;
        }
        
        vector<int> bx(n);
        for (int i = 0; i < n; i++)
        {
            int tmp;
            cin >> tmp;
            tmp--;
            bx[tmp] = i;
        }
        
        vector<int> cx(n);
        for (int i = 0; i < n; i++)
        {
            int tmp;
            cin >> tmp;
            tmp--;
            cx[tmp] = i;
        }
        
        long long r = 0;
        
        for (int i = 0; i < n - 1; i++)
            for (int j = i + 1; j < n; j++)
                r += (ax[i] < ax[j]) == (bx[i] < bx[j]) && (bx[i] < bx[j]) == (cx[i] < cx[j]);
                
        cout << r << "\n";
    return 0;
}

我认为列表中的更改计数可能会有所帮助：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<int> a(n); 
    vector<int> t(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        a[i]--;
        t[a[i]] = i;
    }


    ll result = 0;
    int l = 1;
    while (l < n) // O(log n)
    {
        vector<int> p((n + l - 1) / 2 / l); 
        for (int i = 0; i < n; i++)
        {
            if (t[i] / l % 2 == 0 && t[i] / l / 2 < p.size())
                p[t[i] / l / 2]++;
            if (t[i] / l % 2 == 1)
                result += p[t[i] / l / 2];
        }

        l *= 2;
    }

    cout << result << "\n";

    return 0;
}
algorithm sorting merge mergesort counting
3个回答
3
投票

您可以在 O(N log2 N) 中解决这个问题，方法是将第一个列表分成两半，以创建前半部分数字的子列表和后半部分数字的子列表。然后：

  1. 将其他两个列表也分为上半场和下半场版本，其中上半场版本包含相同顺序的上半场数字，下半场版本包含下半场数字同样的顺序。

  2. 计算上半数与下半数的所有有效配对。您可以在 O(N log N) 时间内完成此操作。

  3. 分别递归上半部分数字和下半部分数字以计算每个子列表中的配对。

剩下的就是弄清楚如何执行步骤 (2)。为了帮助可视化，我将每个数字称为一个点，它在列表 2 中的位置称为“x”，它在列表 3 中的位置称为“y”。

因此，要找到有效的上半场和下半场点对，首先按 y 对每一半中的点进行排序，然后初始化一个按 x 对点进行排序的空序统计树。

然后按y顺序遍历所有的点（即原来的list 3）：

  • 对于每个上半场点，将其添加到订单统计树中；和

  • 对于每个下半点，检索树中x较小的点数，并将其添加到总数中。

请注意，对于您计算的每一组分数，它们都出现在列表 1 的下半场分数之前，因为它们是上半场分数。它们都出现在 list3 的下半点之前，因为 y 顺序中的出现时间较早。它们都出现在列表 2 的下半点之前，因为这就是我们使用顺序统计树的原因。

1
投票

Matt answer 的 Python 实现。使用 SortedList 的那个。使用列表的是 O(n²) 而不是 O(n log² n) 因为插入需要线性时间，但它在实践中仍然很快并且不使用第三方包。

from itertools import combinations
import random
from sortedcollections import SortedList
from time import perf_counter as time
from bisect import bisect 

def naive(A, B, C):
    return len(set.intersection(*(
        set(combinations(s, 2))
        for s in [A, B, C]
    )))


def Matt_SortedList(A, B, C):
    if len(A) < 2:
        return 0
    m = len(A) // 2
    left = set(A[:m])
    findx = {b: x for x, b in enumerate(B)}
    xs = SortedList()
    count = 0
    for y, c in enumerate(C):
        x = findx[c]
        if c in left:
            xs.add(x)
        else:
            count += xs.bisect(x)
    count += Matt_SortedList(
        A[:m],
        [b for b in B if b in left],
        [c for c in C if c in left]
    )
    count += Matt_SortedList(
        A[m:], 
        [b for b in B if b not in left],
        [c for c in C if c not in left]
    )
    return count


def Matt_list(A, B, C):
    if len(A) < 2:
        return 0
    m = len(A) // 2
    left = set(A[:m])
    findx = {b: x for x, b in enumerate(B)}
    xs = []
    count = 0
    for y, c in enumerate(C):
        x = findx[c]
        i = bisect(xs, x)
        if c in left:
            xs.insert(i, x)
        else:
            count += i
    count += Matt_list(
        A[:m],
        [b for b in B if b in left],
        [c for c in C if c in left]
    )
    count += Matt_list(
        A[m:], 
        [b for b in B if b not in left],
        [c for c in C if c not in left]
    )
    return count


funcs = naive, Matt_SortedList, Matt_list

n = 1000
for _ in range(3):
    A, B, C = (
        random.sample(range(1, n+1), n)
        for _ in range(3)
    )
    for f in funcs:
        t = time()

        print(f(A, B, C), f'{(time()-t)*1e3:5.1f} ms ', f.__name__)
    print()

长度为 1,000 的随机列表的三个测试的输出和时间：

129600 780.8 ms  naive
129600  22.7 ms  Matt_SortedList
129600  14.2 ms  Matt_list

122571 741.4 ms  naive
122571  22.1 ms  Matt_SortedList
122571  13.7 ms  Matt_list

120176 698.5 ms  naive
120176  22.3 ms  Matt_SortedList
120176  13.8 ms  Matt_list

100,000 到 1,000,000 长度的快速解决方案：

100,000:
1252085208 4321.7 ms  Matt_SortedList
1252085208 2970.1 ms  Matt_list

200,000:
4988226746 10.18 s  Matt_SortedList
4988226746  7.80 s  Matt_list

500,000:
31262040091 28.40 s  Matt_SortedList
31262040091 27.09 s  Matt_list

1,000,000:
125081735840 63.35 s  Matt_SortedList
125081735840 80.81 s  Matt_list
0
投票

假设三个输入排列是 A、B、C。

找到使 A 和 B 的第一个 elt 与 C 的第一个 elt 相匹配的移位数。同上 C 中从左到右的后续 elt。对于 C 中的每个 elt，取 A B 中移位的最大值。将这些求和以获得无序对的数量。从 choose(n, 2) 中减去。

例如

A  1,2,3,4,5
B  4,2,1,5,3
C  3,4 5,2,1

AC 2,2,2,1,0
BC 4,0,2,0,0

mx 4,2,2,1,0

sum = 9
choose(5,2) - 9 = 1

例如

A    1,2,3,4,5,6
B    4,2,5,6,1,3
C    1,6,2,5,3,4
-----------------
AC   0,4,0,2,0,0
BC   4,3,1,1,1,0
-----------------
max  4,4,1,2,1,0

sum = 12
choose(6,2) - 12 = 3

3个是：13、23、25

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.