假设我有两个数组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).