algorithm - 计算二维对数组中的反转

Question

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

Answer 1

它是对熟悉的归并排序倒数计数算法的简单修改，可以用来解决这个问题，所以让你充分理解它是一个先决条件。

如果我们检查这个算法的合并步骤，我们有 2 个已排序的半部分和 2 个指向每个部分的元素的指针。让我们的左指针是i，我们的右指针是j。使用反转的传统定义，如果我们的i指针指向的值大于当时指向的值，j因为数组正在排序并且左侧的所有元素都在真实数组中的右侧之前，我们知道从i左半部分到末尾的所有元素都符合我们对值反转的定义，j因此我们将计数增加左半部分末尾的位置mid - i。mid

切换回您的问题，我们正在处理 pair (x,y)。如果我们可以保持我们的x值排序，那么使用上述方法，我们可以简单地计算仅考虑x值的反转次数。看看你对半倒置的定义，如果我们只计算，我们肯定会过度计算我们需要的数字xi > xj。我们错过了yi >= y' > yj必须从我们的计数中过滤掉的额外约束。

因此，如果我们回顾我们的传统算法，当我们的i指针指向的值大于 at 的值时，j我们还需要确保我们的y值 atj小于y'。如果这不是真的，那么x从i到到的任何一个都mid不会符合我们对半倒置的定义，因此我们无法计算它们。现在让我们假设我们j的 'y小于，如果我们简单地计算从到y'的所有对，那么我们仍然会过度计算具有 的对。imidyi < y'

解决此问题的一种方法是跟踪y左半部分中的值i，mid并将>= y'该值添加到我们的计数中。我们可以跟踪y >= y'在合并步骤中看到的数量到 any ，然后从左半部分的'si总数中减去。为了跟踪这个总数，我们可以从我们的递归函数中返回那个值（total = left + right），并且在合并时只使用来自左半部分的数字。我们还需要修改我们的基本情况，这很简单。y>= y'

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))