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

Question

给定两个数组

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

两者的编号相同，但顺序不同。 我们必须对两者 进行排序。条件是您不能比较同一数组中的元素。

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))。