计算二维对数组中的反转

Question

问题描述：
假设有一个二维对数组 ((x1, y1), . . . ,(xn, yn)) .使用 fixed 常量如果 i < j, xi > xj 并且 yi ≥ y' > yj ，则 y' 一对 (i, j) 被称为半反转。设计一个算法计算半反转对的数量。如果你的算法是，你将获得满分正确的复杂度不超过 O(n log n)。 \我的想法是使用与普通数组中的倒置计数类似的方法来处理这个问题，但我的问题是我们如何在合并和计数步骤中保持顺序？

Answer 1

对大家熟悉的merge-sort反转计数算法进行了简单的修改，可以用来解决这个问题，让你充分理解它为前提。

如果我们检查这个算法的合并步骤，我们有 2 个排序的一半和 2 个指向每个元素的指针。设左指针为 i，右指针为 j。使用反转的传统定义，如果我们的 i 指针指向的值大于 j 指向的值，那么由于数组被排序并且左边的所有元素都在那些元素之前在实际数组的右侧，我们知道从 i 到左半部分末尾的所有元素都符合我们对 j 值的反转定义，因此我们将计数增加 mid - i 其中 mid 是左半部分的结尾。

回到你的问题，我们正在处理对 (x,y)。如果我们可以保持我们的 x 值排序，那么使用上述方法，我们可以简单地计算仅考虑 x 值的反转次数。查看您对半反转的定义，如果我们只计算 xi > xj，我们肯定会多算我们需要的数量。我们缺少 yi >= y' > yj 的附加约束，它必须从我们的计数中过滤掉。

因此，如果我们回顾一下我们的传统算法，当我们的 i 指针指向的值大于 j 处的值时，我们也需要确保我们在 j 处的 y 值小于 y'。如果这不是真的，那么从 i 到 mid 的 x 中的 none 将符合我们对半反转的定义，因此我们不能计算它们。现在让我们假设我们的 j 的 y 小于 y'，如果我们简单地计算从 i 到 mid 的所有对，那么我们仍然会结束计算具有 yi < y'.

的对

解决此问题的一种方法是跟踪从 i 到 mid 的左半部分 y 值，即 >= y' 并添加该值据我们统计。我们可以跟踪我们在合并步骤中看到的 y >= y' 到任何 i，并从 y 的总数中减去它 >= y'左半边。为了跟踪总数，我们可以 return 来自递归函数的值（总数 = 左 + 右），并且在合并时仅使用来自左半部分的数字。我们还需要修改我们的基本案例，这很简单。

def count_half_inversions(l, y):
    return count_rec(l, 0, len(l), l.copy(), y)[0]

def count_rec(l, begin, end, copy, y):
    if end-begin <= 1:
        # we have only 1 pair
        return (0, 1 if l[begin][1] >= y else 0)
    mid = begin + ((end-begin) // 2)
    left = count_rec(copy, begin, mid, l, y)
    right = count_rec(copy, mid, end, l, y)
    between = merge_count(l, begin, mid, end, copy, left[1], y)
    # return (inversion count, number of pairs, (i,j), with j >= y)
    return (left[0] + right[0] + between, left[1] + right[1])

def merge_count(l, begin, mid, end, copy, left_y_count, y):
    result = 0
    i,j = begin, mid
    k = begin
    while i < mid and j < end:
        if copy[i][0] > copy[j][0]:
            if y > copy[j][1]:
                result += left_y_count
            smaller = copy[j]
            j += 1
        else:
            if copy[i][1] >= y:
                left_y_count -= 1
            smaller = copy[i]
            i += 1
        l[k] = smaller
        k += 1
    while i < mid:
        l[k] = copy[i]
        i += 1
        k += 1
    while j < end:
        l[k] = copy[j]
        j += 1
        k += 1
    return result
                
test_case = [(1,1), (6,4), (6,3), (1,2), (1,2), (3,3), (6,2), (0,1)]
fixed_y = 2

print(count_half_inversions(test_case, fixed_y))

计算二维对数组中的反转

Counting inversions in an array of 2D pair

algorithm

divide-and-conquer