与给定数组最近的排列

Question

问题

我有两个整数数组A[]和B[]。数组B[]是固定的，我需要找出A[]的排列，它比B[]小得多，而且排列离B[]最近。我的意思是：

对于I in (0 <= i< n)，abs(Bi-Ai)最小，A[]应小于B[] 孤立性。

例如，：

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

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

因此，A[]与B[]的可能最近排列是

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

My Approach

尝试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 N)时间和O(m)额外空间，其中n是A的总元素数，m是不同元素的数目。(由于m，m，c，c，≤，n，n，N，C，N，N)，我们也可以将其表示为O(n，n，log，n)时间和O(n)额外空间。

注意，如果没有解决方案，那么回溯步骤将一直到达i == -1。如果发生这种情况，您可能会想要引发一个例外。

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

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

要想在词汇表上更小，数组必须有一个从左到右的初始可选部分，其中A[i] = B[i]以元素A[j] < B[j]结尾。为了最接近B，我们希望最大化该区段的长度，然后最大化数组的其余部分。

因此，考虑到这个总结，另一种方法是执行两个单独的循环，其中第一个循环决定初始部分的长度，第二个循环实际上填充A。这相当于上述方法，但可能会产生更清晰的代码。所以：

1. 构建A不同元素计数的有序映射。
2. 初始化initial_section_length := -1。
3. 迭代数组索引0到n−1，从这个映射中“提取”元素。对于每个索引：
   • 如果可以选择一个比A的当前元素少的尚未使用的B元素，那么将initial_section_length设置为当前数组索引。(否则，不要。)
   • 如果无法选择与当前A元素相同的A中尚未使用的元素，则退出此循环。(否则，继续循环。)

​

1. 如果是initial_section_length == -1，那么就没有解决方案；引发异常。
2. 重复步骤1:重新构建有序的地图.
3. 迭代从0到initial_section_length-1的数组索引，从映射中“提取”元素。对于每个索引，选择一个尚未使用的A元素，该元素等于B的当前元素。(第一个循环确保了这样一个元素的存在。)
4. 对于数组索引initial_section_length，选择比B当前元素少的A中最大的尚未使用的元素(并将其从地图中“提取”)。(第一个循环确保了这样一个元素的存在。)
5. 迭代从initial_section_length+1到n−1的数组索引，继续从映射中“提取”元素。对于每个索引，选择尚未使用的A中最大的元素。

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

Answer 2

存在n!排列的A[n] (如果有重复元素，则减少)。

利用范围0..n!-1上的二值搜索确定A[] (任意找到的例子)的第k次字典排列，它与B[]最接近。

也许在C++中，您可以利用std::lower_bound

Answer 3

基于对您问题的注释部分的讨论，您将寻找一个完全由向量A的元素组成的数组，即--在字典顺序中--与向量B最接近。

对于这个场景，算法变得非常简单。这个想法与@ruakh的答案中已经提到的相同(尽管他的回答提到了你的问题的一个更早、更复杂的版本-这一点仍然体现在OP中-因此更加复杂)：

• A类
• 在B上循环，并选择最接近Bi的元素A。从列表中删除该元素。
• 如果A中没有任何元素比Bi小或等于，则选择最大的元素。

以下是基本实现：

#include <string>
#include <vector>
#include <algorithm>

auto get_closest_array(std::vector<int> A, std::vector<int> const& B)
{
    std::sort(std::begin(A), std::end(A), std::greater<>{});

    auto select_closest_and_remove = [&](int i)
    {
        auto it = std::find_if(std::begin(A), std::end(A), [&](auto x) { return x<=i;});
        if(it==std::end(A))
        {
            it = std::max_element(std::begin(A), std::end(A));            
        }
        auto ret = *it;
        A.erase(it);
        return ret;
    };

    std::vector<int> ret(B.size());
    for(int i=0;i<(int)B.size();++i)
    {
        ret[i] = select_closest_and_remove(B[i]);
    }
    return ret;
}

应用于OP one中的问题：

int main()
{
    std::vector<int> A ={1,3,5,6,7};
    std::vector<int> B ={7,3,2,4,6};

    auto C = get_closest_array(A, B);

    for(auto i : C)
    {
        std::cout<<i<<" ";
    }
    std::cout<<std::endl;
}

它展示了

7 3 1 6 5

这似乎是想要的结果。