C++实用技巧——离散化( 五 )

2019-10-09

.v;

a[i
.id=i;

sort(a+1a+n+1);

for(int i=1;i<=n;i++)

rank[a[i
.id
=i;

这种方法复杂度比上面那一种要优，但不能处理重复元素。它直接用结构体存储原本的数列的元素的位置，然后排序以后将他们再重新赋值。那么rank[
就是结构体a[
离散化后的结果。

v: 3 6 5 10 8

id : 1 2 3 4 5

排序以后：

v: 3 5 6 8 10

id: 1 3 2 5 4

所以离散化以后：

v: 3 5 6 8 10

id: 1 3 2 5 4

rk: 1 2 3 4 5

推荐阅读

上一篇：NEX 3、Mate30 Pro上演双强之争，消费者选哪个？

下一篇：C++中命名空间的五大常见用法