对坐标点的离散化

很多时候会遇到一类题， 这类题点的个数很少 ， 但是每个点的数据特别大 , 这时基本有两种想法 。

1 . 用map 处理 ， map 是一个关联容器 ， 可以实现元素的一对一 ， 用map 后 ， 你就可以实现对数据的桶排了。

2 . 对数据离散化处理

　　先是点的离散化 例如 只有 3 个数据 ， 9 20 33 他们的关系就可以映射成 1 2 3

　　怎么处理呢 ？

　　　　在两个数组中存原有数据， 对第一数组进行排序， 用的时候 用第二个数组 中的数在第一个数组中二分搜索下下标位置，即为映射好的数据。

　　区间的映射怎么解决呢？

　　　　用结构体去存区间的每个点，在将所有的点存在一个数组中，同样的方法对其操作。但是这样会有一个弊端，例如 1 - 10  1 - 4  6 - 8 三段区间映射的话，会被映射成 1 - 5   1 - 2   3 - 4  这样看映射后的区间 是都连起来的 ， 但实际呢 ？ 并不是这样的，因此可以这样解决这个问题 。

　　　　在将所有的点存入数组后， 对数组进行排序后，相邻的两点间如果他们之间的差大于 1 就在他们之间任意插入一个他们之间的元素 。

　　代码实现 ：

　　

// 数组插入新的元素
for(int i = k - 1; i >= 1; i--){
    if (pre[i] != pre[i-1]+1) pre[k++] = pre[i-1]+1;
}

另外 还有一步是对数组中的元素去重

// 数组元素去重
int k = 1;
for(int i = 1; i < n; i++){
    if (pre[i] != pre[i-1]) pre[k++] = pre[i];
}