数组排列，以使一个数组中的最大元素数更多 [英] Arrangement of arrays such that maximum number of elements are greater in one array

问题描述

假设我有两个数组A和B(两个元素数量相等)

Assuming I have two arrays A and B (Both with equal number of elements)

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

我必须以数组A中元素的最大数量大于数组B中它们各自的元素的方式重新排列数组A.

I have to rearrange array A in such a way that maximum number of elements in Array A are greater than their respective elements in array B.

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

In this case, rearranging A as {40,70,50} would yield the required result.

进行此操作的最佳方法是什么?

What would be the most optimal way of going this?

推荐答案

我会使用类似的东西:

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;
}

演示

复杂度: O(n log n).

这篇关于数组排列，以使一个数组中的最大元素数更多的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！