根据与另一个元素顺序不同的数组进行比较，对数组进行排序

Question

给定两个数组

a[] = {1,3,2,4} 
b[] = {4,2,3,1} 

两个数组中的数字相同，但顺序不同。我们需要对它们两个进行排序。条件是不能比较同一数组内的元素。

- shreyasva

---

这对任何人都有意义吗？ - spender

我不太明白。您是要将b转换为与a相同的顺序吗？如果是这样，那么您不是总是返回a吗？ - Gian

如果面试问题是这样的话，我会放弃这个工作机会。真的。 - spender

来吧，这根本不是最奇怪的面试问题。接受现实吧。 - Mu Qiao

@Mu Qiao - 在您查看之前，它被编辑器修复之前是有问题的。 - hatchet - done with SOverflow

Answer 1

我可以给你提供一个基于快速排序的O(N*log(N))时间复杂度的算法。

1. 随机选择数组A中的一个元素a1
2. 使用a1将数组B进行划分，注意只需将数组B中的每个元素与a1进行比较
3. 划分返回位置b1。使用b1将数组A进行划分（与步骤2相同）
4. 如果划分得到的子数组长度大于1，则回到步骤1进行递归操作。

时间复杂度：T(N) = 2*T(N/2) + O(N)。根据主定理，总体复杂度为O(N*log(N))。

- Mu Qiao

Answer 2

我不确定我是否正确理解了问题，但从我的理解来看，任务如下：

对给定的数组 a 进行排序，不直接比较 a 中的任意两个元素。然而，我们有一个第二个数组 b，保证包含与 a 相同的元素，但顺序是任意的。您不允许修改 b（否则只需对 b 进行排序并返回即可...）。

如果 a 中的元素是不同的，那么这很容易：对于 a 中的每个元素，计算在 b 中有多少元素比它小。这个数字给出了按排序顺序的（从零开始的）索引。

对于元素不一定不同的情况留给读者自己思考 :)

- dcn

---

正确的工作解决方案。它是O(n^2)的。期望的解决方案应该是O(nlogn)。 - shreyasva

当然，你可以构建一个b的二叉搜索树，使其达到O(nlogn)，但这与立即对b进行排序是一样的... - dcn