c++ - 给定数组的最近排列

Question

问题

我有两个整数数组 A[]和 B[] .数组 B[]是固定的，我需要找到 A[] 的排列在字典上小于 B[]并且排列最接近 B[] .这里我的意思是:

for i in (0 <= i < n) abs(B[i]-A[i]) is minimum and A[] should be smaller than B[] lexiographically.

例如:

A[]={1,3,5,6,7}

B[]={7,3,2,4,6}

所以，可能是 A[] 的最近排列至 B[]是

A[]={7,3,1,6,5}

我的方法

尝试 A[] 的所有排列然后将其与 B[] 进行比较.但时间复杂度为 (n! * n)
那么有没有办法优化这个呢？

编辑
n可以大到10^5
为了更好的理解

Answer 1

首先，构建 A 的不同元素计数的有序映射。 .

然后，向前迭代数组索引(0 到 n-1)，从此映射中“撤回”元素。在每一点上，有三种可能性:

如 i < n-1 , 并且可以选择 A[i] == B[i] ，这样做并继续向前迭代。

否则，如果可以选择 A[i] < B[i] ，为 A[i] < B[i] 选择最大的可能值.然后继续为所有后续数组索引选择最大的可用值。 (此时您不再需要担心维护 A[i] <= B[i] ，因为我们已经在索引 where A[i] < B[i] 之后。)返回结果。

否则，我们需要回溯到最后一个可以选择 A[i] < B[i] 的索引。 ，然后使用上一个要点中的方法。

请注意，尽管需要回溯，但这里最糟糕的情况是三遍:使用第一个要点中的逻辑向前传递一次，在回溯中向后传递以找到最后一个索引，其中 A[i] < B[i]是可能的，然后使用第二个要点中的逻辑进行最后的前传。

由于维护有序映射的开销，这需要 O(n log m) 时间和 O(m) 额外空间，其中 n 是 A 的元素总数m 是不同元素的数量。 (由于 m ≤ n，我们也可以将其表示为 O(n log n) 时间和 O(n) 额外空间。)

请注意，如果没有解决方案，则回溯步骤将一直到达 i == -1 .如果发生这种情况，您可能希望引发异常。

编辑添加(2019-02-01):

在现已删除的答案中，גלעד ברקן 以这种方式总结了目标:

To be lexicographically smaller, the array must have an initial optional section from left to right where A[i] = B[i] that ends with an element A[j] < B[j]. To be closest to B, we want to maximise the length of that section, and then maximise the remaining part of the array.

所以，考虑到这个总结，另一种方法是做两个单独的循环，其中第一个循环确定初始部分的长度，第二个循环实际上填充 A .这等效于上述方法，但可能会使代码更清晰。所以:

构建 A 的不同元素计数的有序映射.

初始化 initial_section_length := -1 .

遍历数组索引 0 到 n-1，从此映射中“撤回”元素。对于每个索引:

如果可以选择一个尚未使用的元素 A小于 B 的当前元素, 设置 initial_section_length等于当前数组索引。 (否则，不要。)

如果无法选择 A 中尚未使用的元素等于 B 的当前元素，跳出这个循环。 (否则，继续循环。)

如 initial_section_length == -1 ，那就没有办法了；引发异常。

重复第 1 步:重新构建有序映射。

遍历从 0 到 initial_section_length-1 的数组索引, 从 map 中“撤回”元素。对于每个索引，选择一个尚未使用的元素 A等于 B 的当前元素. (第一个循环确保了这样一个元素的存在。)

对于数组索引 initial_section_length ，选择 A 中最大的尚未使用的元素小于 B 的当前元素(并从 map 中“撤回”它)。 (第一个循环确保了这样一个元素的存在。)

遍历来自 initial_section_length+1 的数组索引到 n-1，继续从 map 中“撤回”元素。对于每个索引，选择 A 中最大的元素尚未使用。

这种方法与基于回溯的方法具有相同的时间和空间复杂性。