时间戳

首页 > 解决方案 > 在 O(n) 中对两个数组进行排序（时间和空间）

algorithm - 在 O(n) 中对两个数组进行排序（时间和空间）

问题描述

给定两个（可能未排序的）数组，A以及交换元素B的操作and ，您需要返回最小的交换次数，以便两个数组严格增加（或者如果不可能）swap(A, B, i)A[i]B[i]-1

我很快就想出了一个贪婪的解决方案（如果你愿意，我可以附上代码）但显然在某些情况下它不会产生正确的答案（我不知道）。

为什么贪婪的方法不够好？达到最少掉期数量的替代方法是什么？

编辑：
这是我的代码

def solution(A, B):
    n = len(A)
    swaps = 0
    for i in range(1, n):

        if A[i] > A[i - 1] and B[i] > B[i - 1]:
            continue

        if A[i] < A[i - 1] and B[i] < B[i - 1]:
            return -1
        elif A[i] < A[i - 1]:
            if B[i - 1] < A[i]:
                A[i], B[i] = B[i], A[i]
                swaps += 1
            else:
                return -1
        else:
            # B[i] < B[i - 1]
            if A[i - 1] < B[i]:
                A[i], B[i] = B[i], A[i]
                swaps += 1
            else:
                return -1


    return swaps

# test
assert(solution([5, 3, 7, 7, 10], [1, 6, 6, 9, 9]))

标签： algorithmdata-structurescomputer-science

解决方案

您可以使用 DP 来实现：

一种方法可以是：对于每一对 A[i] 和 B[i]，我们可以选择交换或不交换。所以我们定义了两个 dp 数组，keep[i] 表示如果我们不交换 A[i] 和 B[i]，交换的最小次数是多少。swap[i] 是交换 A[i] 和 B[i] 的最小交换次数。

  • A[i] > A[i -1] && B[i] > B[i - 1]，如果我们选择保留，我们应该保留之前的i-1个元素。所以keep[i] = keep[i - 1] 如果我们选择交换，为了保持排序顺序，我们必须交换前面的第i-1个元素。所以交换[i] = 交换[i - 1] + 1;

  • A[i] > B[i - 1] && B[i] > A[i - 1] 如果我们选择保持，keep[i] = Math.min(keep[i], swap[i - 1])如果我们选择交换，swap[i] = Math.min(swap[i], keep[i - 1] + 1)

  • 对于 A[i] < B[i - 1] 等情况，返回 -1

时间复杂度：O(n)

推荐阅读