数组排列，以使一个数组中的最大元素数更多

本文介绍了数组排列，以使一个数组中的最大元素数更多的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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