c++ - 排列数组，使一个数组中的最大元素数更大

Question

假设我有两个数组 A 和 B(都具有相同数量的元素)

int A[] = {40,50,70};
int B[] = {80,60,45};

我必须重新排列数组 A，使数组 A 中的最大元素数大于数组 B 中它们各自的元素数。

在这种情况下，将 A 重新排列为 {40,70,50} 会产生所需的结果。

执行此操作的最佳方法是什么？

Answer 1

我会使用类似的东西:

std::vector<int> f(std::vector<int> A, const std::vector<int>& B)
{
    std::vector<std::size_t> indexes(B.size());
    std::iota(indexes.begin(), indexes.end(), 0);

    std::sort(A.begin(), A.end(), std::greater<>{});
    std::sort(indexes.begin(), indexes.end(),
              [&B](std::size_t lhs, std::size_t rhs){ return B[lhs] > B[rhs]; });

    auto it = A.begin();
    auto rit = A.rbegin();
    std::vector<int> res(A.size());
    for (auto index : indexes) {
        if (*it > B[index]) {
            res[index] = *it;
            ++it;
        } else {
            res[index] = *rit;
            ++rit;
        }
    }
    return res;
}

Demo

复杂度:O(n log n)。