给定数组的最近置换

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

N

• 如果 i < n-1 ,并且可以选择 A[i] == B[i]
• A[i] < B[i] ,选择的最大可能值 A[i]<B[i] . 然后继续为所有后续数组索引选择最大的可用值。(此时,您不再需要担心维护 A[i] <= B[i] ,因为我们已经在寻找一个索引
• 否则,我们需要回溯到它所在的最后一个索引 可以选择 A[i]<B[i]
  • 请注意,尽管需要回溯,这里最糟糕的情况是三次传递:一次使用第一个项目符号中的逻辑向前传递,一次回溯中的向后传递以查找最后一个索引,其中 这是可能的,然后使用第二个要点中的逻辑进行最后一次向前传球。

由于维护有序映射的开销,这需要 ( N 日志 ( M )额外空间,在哪里 N 全部的 元素数 A. 和 你的电话号码是多少 M ,我们也可以表示为 ( 日志 O N )额外空间。)

i == -1 . 如果发生这种情况,您可能希望引发异常。

在现已删除的答案中,××××××ק××以如下方式总结了目标:

若要在字典上更小,数组必须从左到右有一个初始可选部分,其中 A[i] = B[i] 以元素结尾 A[j] < B[j] B ,我们希望最大化该部分的长度,然后最大化阵列的其余部分。

因此,记住这个总结,另一种方法是做两个单独的循环,其中第一个循环确定初始部分的长度,第二个循环实际填充 A.

1. 构建不同元素计数的有序映射 A.
2. initial_section_length := -1 .
3. N 1.从该映射中“提取”元素。对于每个索引:
   • A. 少于 当前元素 设置 initial_section_length 等于当前数组索引。(否则,请不要)
   • 不 可以选择尚未使用的元素 A. 那是 当前元素 ,打破这个循环。(否则,请继续循环。)
4. initial_section_length == -1 ,那么就没有解决方案;提出一个例外。
5. 重复步骤1:重新构建有序映射。
6. 迭代从0到0的数组索引 initial_section_length-1 ,从映射中“提取”元素。对于每个索引,选择一个尚未使用的 B . (第一个循环确保了此类元素的存在。)
7. 用于数组索引 ,选择尚未使用的最大元素 A. B (并将其从地图中“撤回”)。(第一个循环确保了此类元素的存在。)
8. initial_section_length+1 到 N A. 那还没用过。

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

有 n! 排列 A[n]

0..n!-1 确定的第k个字典排列 A[] ( arbitrary found example B[]

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

根据问题注释部分的讨论,您将寻找完全由向量元素组成的数组 A 也就是说,在词典排序中,最接近向量 B .

对于这种情况,算法变得非常简单。这个想法与@ruakh的答案中已经提到的想法相同(尽管他的答案指的是你的问题的一个更早更复杂的版本——仍然显示在OP中——因此更复杂):

• 排序A
• 在B上循环并选择A中最接近B[i]的元素。从列表中删除该元素。

以下是基本实现:

#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 gets中的问题:

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