arrays - 最大化数组中的反转计数

Question

我们得到一个未排序的整数数组 A(允许重复)，大小 N 可能很大。我们可以计算索引为 i < j 的对的数量，其中 A[i] < A[j]，我们称之为 X。

我们可以更改数组中的最大一个元素，代价等于绝对值的差值(例如，如果我们用新数字 k 替换索引 K 上的元素，则代价 Y 为 | A[k] - K | )。我们只能用数组中找到的其他元素替换此元素。

我们想找到 X + Y 的最小可能值。

一些例子:

• [1,2,2] 应返回 1(将 1 更改为 2，使数组变为 [2,2,2])
• [2,2,3] 应返回 1(将 3 更改为 2)
• [2,1,1] 应返回 0(因为不需要更改)
• [1,2,3,4] 应该返回 6(这已经是可能的最小值)
• [4,4,5,5] 应该返回 3(这可以通过将前 4 变为 5 或将最后 5 变为 4 来实现)

可以使用简单的 O(n²) 解决方案找到对的数量，在 Python 中:

def calc_x(arr):
    n = len(arr)
    cnt = 0
    for i in range(n):
        for j in range(i+1, n):
            if arr[j] > arr[i]:
                cnt += 1    
    return cnt

暴力解决方案很容易编写，例如:

def f(arr):
    best_val = calc_x(arr)
    used = set(arr)
    for i, v in enumerate(arr):
        for replacement in used:
            if replacement == v:
                continue

            arr2 = arr[0:i] + replacement + arr[i:]

            y = abs(replacement - v)
            x = calc_x(arr2)

            best_val = min(best_val, x + y)
    return best_val

我们可以计算每个元素在 O(n*log(n)) 中大于其自身的项目数，例如使用 AVL 树或合并排序的一些变体。但是，我们仍然需要寻找改变哪些元素以及它可以实现哪些改进。

这是作为一个面试问题给出的，我想要一些关于如何有效解决这个问题(数据结构或算法)的提示或见解。

Answer 1

在计算反转时，一定要达到 O(n log n) 的复杂度。

我们可以看到，当您更改索引 k 处的值时，您可以:

1)增加它，然后可能减少元素大于k的反演次数，但增加元素小于k的反演次数

2) 减少它(相反的事情发生)

我们尽量不要每次更改值时都计算 x。您需要了解什么？

案例一):

你必须知道左边有多少元素小于你的新值v，右边有多少元素大于你的值。您可以很容易地在 O (n) 中检查它。那么你现在的x是多少？您可以使用以下公式对其进行计数:

prev_val - your previous value
prev_x - x that you've counted at the beginning of your program
prev_l - number of elements on the left smaller than prev_val
prev_r - number of elements on the right bigger than prev_val
v - new value
l - number of elements on the right smaller than v
r - number of elements on the right bigger than v

new_x = prev_x + r + l - prev_l - prev_r

在第二种情况下，你几乎做相反的事情。

现在你得到的是 O( n^3 ) 而不是 O (n^3 log n)，这可能仍然很糟糕。不幸的是，这就是我现在想到的。如果我想出更好的东西，我一定会告诉你。

编辑:内存限制如何？有没有？如果没有，您可以只为数组中的每个元素制作两个集合，其中包含当前元素之前和之后的元素。然后你可以在 O (log n) 中找到更小/更大的数量，使你的时间复杂度为 O (n^2 log n)。

编辑 2:我们还可以尝试检查，对于每个可能的值 v，哪个元素最适合更改为值 v。您可以制作两个集合并在检查每个元素时从中添加/删除元素，使时间复杂度为 O(n^2 log n) 而无需使用太多空间。所以算法将是:

1) 确定你可以改变任何元素的每一个值v，计算x

2) 对于每个可能的值 v:

• 制作两个集合，将所有元素插入第二个集合
• 对于数组中的每个元素 e:将先前的元素(如果有的话)添加到第一个集合并从第二个集合中删除元素 e，然后计算集合 1 和 2 中较大/较小元素的数量并计算新的 x

编辑 3:您可以使用前缀总和作为一个值，而不是制作两组。这已经是 O (n^2)，但我认为我们可以做得更好。