基于与不同顺序的相同元素的另一个数组的比较对数组进行排序

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