离散化+unique函数+lower_bound函数等等函数的集合

2018/03/06 19:34
阅读数 49

有些数据本身很大, 自身无法作为数组的下标保存对应的属性。

如果这时只是需要这堆数据的相对属性, 那么可以对其进行离散化处理!

离散化:当数据只与它们之间的相对大小有关,而与具体是多少无关时,可以进行离散化。

例如

9 1 0 5 4 与 5 2 1 4 3 的逆序对个数相同。
设有4个数:
1234567、123456789、12345678、123456
排序:123456<1234567<12345678<123456789
           =>     1     <        2       <        3       <        4
那么这4个数可以表示成:2、4、3、1

使用STL算法离散化:
思路:先排序,再删除重复元素,然后就是索引元素离散化后对应的值。
假定待离散化的序列为a[n],b[n]是序列a[n]的一个副本,则对应以上三步为:

 

sort(sub_a,sub_a+n);
int size=unique(sub_a,sub_a+n)-sub_a;//size为离散化后元素个数
for(i=0;i<n;i++) a[i]=lower_bound(sub_a,sub_a+size,a[i])-sub_a + 1;//k为b[i]经离散化后对应的值

 

对于第3步,若离散化后序列为0, 1, 2, ..., size - 1则用lower_bound,从1, 2, 3, ..., size则用upper_bound,其中lower_bound返回第1个不小于b[i]的值的指针,而upper_bound返回第1个大于b[i]的值的指针,当然在这个题中也可以用lower_bound然后再加1得到与upper_bound相同结果,两者都是针对以排好序列。使用STL离散化大大减少了代码量且结构相当清晰。

 

 

STL中的unique函数的头文件:

#include<iostream>
  • 1

unique 的作用是“去掉”容器中相邻元素的重复元素,这里所说的“去掉”并不是真正把重复元素删除,它实质上是一个伪去除,是把重复的元素移到后面去了,然后依然保存到了原数组中,然后返回去重后最后一个元素的地址。 
因为unique去除的是相邻元素的重复元素,所以使用之前需要排序。

sort, unique和erase的联合使用,可以将一个有重复元素的数组的重复元素去除,从而转化成一个无重复元素的有序数组。

end_unnique = unique(result.begin(), result.end());
result.erase(end_unique, result.end());
  • 1
  • 2

由于 end_unique返回去重后最后一个元素的位置,而重复的元素都被移动到后面去了,所以要将从去重后最后一个元素的地址 到 原数组最后一个地址 这些地址中的元素去掉,从而得到无重复元素的数组。

 

STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间(当然这也是运用二分查找的前提),下面记录一下这两个函数。

ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于值val的位置。

 

 

Lower_bound  解释

函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置

举例如下:

一个数组number序列为:4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标

pos = lower_bound( number, number + 8, 3) - number,pos = 0.即number数组的下标为0的位置。

pos = lower_bound( number, number + 8, 9) - number, pos = 1,即number数组的下标为1的位置(即10所在的位置)。

pos = lower_bound( number, number + 8, 111) - number, pos = 8,即number数组的下标为8的位置(但下标上限为7,所以返回最后一个元素的下一个元素)。

所以,要记住:函数lower_bound()在first和last中的前闭后开区间进行二分查找,返回大于或等于val的第一个元素位置。如果所有元素都小于val,则返回last的位置,且last的位置是越界的!!~

返回查找元素的第一个可安插位置,也就是“元素值>=查找值”的第一个元素的位置

 

 

upper_bound 解释

 

 

位运算的百度百科:https://baike.baidu.com/item/位运算符/2786163?fr=aladdin

展开阅读全文
c++
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部