给定数组最近的排列

Question

题

我有一个整数两个数组A[]和B[].数组B[]是固定的,我需要找到其排列A[]规则小于B[]和排列最接近的排列B[].我的意思是:

对于i in(0 <= i <n),abs(B [i] -A [i])是最小的并且A[]应该小于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],因为我们已经在索引之后A[i] < B[i].)返回结果.
否则,我们需要回溯到最后一个索引它是可能的选择A[i] < B[i],然后用前面的项目点的方法.
- 请注意,尽管需要回溯,但这里最糟糕的情况是三次传递:一次使用第一个项目符号点中的逻辑传递,一次向后传递回溯以查找A[i] < B[i]可能的最后一个索引,然后是最后一次传递使用第二个项目符号中的逻辑传递.

由于维护有序映射的开销,这需要O(n log m)时间和O(m)额外空间,其中n是元素的总数A,m是不同元素的数量.(由于米 ≤ ñ,我们也可以表达这种Ø(ñ 日志 ñ)时间和Ø(ñ)额外的空间.)

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

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

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

要在字典上缩小,数组必须具有从左到右的初始可选部分,其中A[i] = B[i]以元素结束A[j] < B[j].为了最接近B,我们希望最大化该部分的长度,然后最大化数组的剩余部分.

因此,考虑到这个总结,另一种方法是做两个单独的循环,其中第一个循环确定初始部分的长度,第二个循环实际填充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"撤消"地图中的元素.对于每个索引,选择一个尚未使用的元素,A该元素等于当前元素B.(第一个循环确保了这种元素的存在.)
对于数组索引initial_section_length,选择最小的尚未使用的元素,A使其小于当前元素B(并从地图中"撤回").(第一个循环确保了这种元素的存在.)
迭代数组索引从ninitial_section_length+1到-1,继续从地图"撤回"元素.对于每个索引,选择尚未使用的最大元素.A

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