离散化思想

1.离散化场景

出现数据范围极大，但是数据量却不大的时候，如果我们要用数据值来映射数组下标，此时数据范围大不好直接映射，我们可以先将数据映射为一个较小的值，然后我们再用离散化后的数据处理问题。

eg：-1e9  <= x <= 1e9

此时不能直接根据x的值映射到数组中，因为x的值太大了，数组要开这么多空间是不允许的

离散化的过程：
1.升序排序数据

2.去重

升序排序并去重后我们就按照数据值的大小给原数据提供从1开始的映射值

图示：

---

2.模板题：

代码实现由两种：

方法一：升序排序+ 去重+二分查找

#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int n;
int cnt;//记录去重后的数据个数
int a[N];//初始数据数组
int disc[N];//离散化后数据
int find(int x)
{int l = 1;int r = cnt;int mid = 0;while (l < r){mid = (l + r) / 2;if (disc[mid] < x){l = mid + 1;}elser = mid;}return l;
}
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];disc[++cnt] = a[i];}sort(disc + 1, disc + 1 + n);//升序排序cnt = unique(disc + 1, disc + 1 + n) - (disc + 1);//去重for (int i = 1; i <= n; i++){cout << a[i] << "的离散化值为" << find(a[i]) << endl;}return 0;
}

注意：

1.unique可以对指定迭代器区间进行去重，并返回去重后的迭代器区间末尾迭代器，所以我们用unique可以完成去重，用他的返回值减去disc+1（区间开始位置迭代器）得到去重后的数据个数

2.find函数作用：利用二分查找的算法将disc数组a[i]值对应的离散化索引找到并返回

方法二：排序+哈希表

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1e5 + 10;
int n;
int cnt;
int a[N];//初始数据数组
int disc[N];//离散化后数据
unordered_map<int, int> m;//原数据值，索引
int main()
{cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];disc[++cnt] = a[i];}sort(disc + 1, disc + 1 + cnt);//升序排序int num = 0;for (int i = 1; i <= n; i++){if (m.count(disc[i])){continue;}num++;m[disc[i]] = num;}for (int i = 1; i <= n; i++){cout << a[i] << "的离散化值为" << m[a[i]] << endl;}return 0;
}

注意：

1.哈希表的key是数据值，value是离散化后的数据值

2.当数据值已经出现过在哈希表中，我们就直接跳过即可，不用重复录入

3.最后是要根据原数据值来查找的，所以我们用a[i]当key