定义：

把无穷大集合中的若干个元素映射为有限集合以便于统计的方法。当数据之间差值很大，即使排完序后，两个数之间仍有很大的差值，不适合直接用下标表示，这样会导致数组开的过大，容量不够，且中间有很多空没有用。针对这种情况，就想到把这间距很大的 m 个数据，在映射到 [1-m] 上，这样就会有效的减少数组的大小，且中间不会有浪费的空间。即把稀疏的数据变的稠密起来。

步骤:

1. 用数组将所有数据存储在一起all[]
2. 对数组all[]进行排序
3. 在开一个数组un[]将排好序的all[]去重并添加到un[]中

此时un[]下标即对应原来数据的离散值。

注意：

查找时可以用二分吗查找（也可以用内置函数lower_bound)

1 //使用库函数
2     int find(int x){
3         return lower_bound(uni+1,uni+1+k,x)-uni;
4     }

 1 //也可以直接二分
 2     int find(int x){
 3         int l=1,r=k+1;
 4         while(l<r){
 5             int mid=(l+r)/2;
 6             if(uni[mid]>=x) r=mid;
 7             else l=mid+1;
 8         }
 9         return r;
10     }

例题

acwing103. 电影、

题目链接

 1 #include<iostream>
 2 #include<algorithm>
 3 #include<cstdio>
 4 
 5 using namespace std;
 6 
 7 const int N = 2e5 + 100;
 8 int a[N], b[N], c[N]; //科学家， 电影语言， 电影字幕
 9 int n, m;
10 int all[3 * N], un[3 * N]; //全部语言， 去重后的语言
11 int cnt;//计数
12 int ans[3 * N];
13 int t;
14 int find(int x) {
15     return lower_bound(un + 1, un + t + 1, x) - un;
16 }
17 
18 int main() {
19     cin >> n;
20     for (int i = 1; i <= n; i ++) {
21         cin >> a[i];
22         all[++cnt] = a[i];
23     }
24 
25     cin >> m;
26 
27     for (int i = 1; i <= m; i ++) {
28         cin >> b[i];
29         all[++cnt] = b[i];
30     }
31 
32     for (int i = 1; i <= m; i ++) {
33         cin >> c[i];
34         all[++cnt] = c[i];
35     }
36 
37     sort(all + 1, all + 1 + cnt);
38     for (int i = 1; i <= cnt; i ++) { //去重并离散化
39         if (i == 1 || all[i] != all[i - 1]) un[++t] = all[i];
40     }
41 
42     int ans1, ans2, ans3;
43     ans1 = ans2 = ans3 = 0;
44 
45     for (int i = 1; i <= n; i ++) { //统计科学家会的语言分类个数
46         ans[find(a[i])] ++;
47     }
48 
49     for (int i = 1; i <= m; i ++) {
50         int anx = ans[find(b[i])], any = ans[find(c[i])];
51         if (anx > ans2 || (anx == ans2 && any > ans3)) {
52             ans1 = i, ans2 = anx, ans3 = any;
53         }
54     }
55 
56     if (ans1 == 0) puts("1");
57     else cout << ans1 << endl;
58 
59     return 0;
60 }