问题
我有两个整数数组A[]和B[]。 数组B[]是固定的，我需要找到比B[]字典序小且最接近B[]的A[]排列。这里我的意思是：
对于i在（0 <= i < n）之间 abs(B[i]-A[i]) 最小，并且
A[]应该比B[]字典序小。
例如：
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。
为了更好地理解
A。这相当于上面的方法，但可能会使代码更清晰。所以：
A中不同元素的计数。initial_section_length := -1。A元素，该元素小于当前B元素，则将initial_section_length设置为当前数组索引。（否则，不执行此操作。）A元素，该元素等于当前B元素，则退出此循环。（否则，继续循环。）initial_section_length == -1，则没有解决方案；抛出异常。initial_section_length-1，“撤回”映射中的元素。对于每个索引，选择一个尚未使用过的A元素，该元素等于当前B元素。（第一个循环确保了这样的元素的存在。）initial_section_length，选择最大的尚未使用的A元素，该元素小于当前B元素（并从映射中“撤回”它）。 （第一个循环确保了这样的元素的存在。）initial_section_length+1到n−1，继续从映射中“撤回”元素。对于每个索引，选择尚未使用的A元素中的最大元素。n!个A[n]的排列（如果有重复元素，则排列数目较少）。0..n!-1内确定A[]的第k个字典序排列，该排列最接近B[]的较小者 (任意找到的例子)。std::lower_bound。根据您问题的评论部分的讨论，您正在寻找一个完全由向量A元素组成的数组，该数组在词典顺序上最接近向量B。
对于这种情况，算法变得非常简单。这个想法与@ruakh的答案中已经提到的一样（尽管他的答案是针对您早期和更复杂的问题版本的 -- 仍然显示在OP中 -- 因此更加复杂）：
以下是基本实现：
#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;
}
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
这似乎是期望的结果。
A = {1,3,4,6,7} 和 B = {7,3,2,4,6}，它给出了 7 3 1 4 6，但我认为OP想要的答案是 7 3 1 6 4（它是所有比 B 字典序小的 A 的排列中字典序最大的）。 - ruakh
C，使得对其使用next_permutation函数可以得到B？ - user58697