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

2019-10-09

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

cin>>a[i
t[i
=a[i
;

sort(t+1t+n+1);

m=unique(t+1t+n+1)-t-1;

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

a[i
=lower_bound(t+1t+m+1a[i
)-t;

在这段代码中， a[
经过离散，范围就变成了m 。解释一下， unique是c++自带的一个函数，表示对一个数列去重，然后返回不重复的元素个数，当然在后面要减去首地址。那么这种离散化对于有重复元素的数列也可以适用，但复杂度相对后面要讲的第二种方法会高些。

比如，这组数据：

123424242654662420

进入这段代码后，首先会排个序得到：

012422422342465466

推荐阅读

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

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