To be better

两个序列按序离散化

2018-06-01 20:32:01


问题

考虑这样一个问题:有两个序列,例如:

3 6 7 4 8

5 2 3 6 7

将第二个序列变成按第一个序列的顺序排列,即:

2 5 6 3 7

如果看下标,则序列二变为:

2 1 4 3 5

求这个数组。

算法

将序列A, B中每个数“绑定”其下标:

struct num {
    int val, idx;
};
num A[N], B[N];
A B
(3,1) (5,1)
(6,2) (2,2)
(7,3) (3,3)
(4,4) (6,4)
(8,5) (7,5)

将A, B序列分别按值排序:

A B
(3,1) (2,2)
(4,4) (3,3)
(6,2) (5,1)
(7,3) (6,4)
(8,5) (7,5)

现在,两个数组就有序了,而 $A[1].idx$ 为1, $B[1].idx$ 为2,所以,A数组的一号位对应着B数组的二号位,同理,A数组的四号位对应着B数组的三号位,A数组的二号位对应着B数组的一号位…… 所以:

c[a[i].idx] = b[i].idx;

c数组即为所求。