在很多情况下，问题的范围虽然定义在整数集合Z，但是只涉及其中m个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）。此时，我们就可以把整数集合Z中的这m个整数与1～m建立映射关系。
通俗来讲，就是把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。
算法流程
-
预处理
-
先将无序数组排序。
-
去重。
-
二分查找
知识拓展
模板
//离散化预处理
inline void discrete()
{
//排序
sort(a + 1,a + n + 1);
//去重
for(int i = 1;i <= n;++i)
{
if(i == 1 || a[i] != a[i-1])
b[++m] = a[i];
}
}
//二分查找 x映射为那个1~m之间的整数
inline int query(int x)
{
return lower_bound(b + 1,b + m + 1,x) - b;
}
查找是为什么要 - b?
通过返回的地址减去起始地址begin,得到找到数字在数组中的下标
++m是m从0开始吗
自己运行一下这个程序你就懂了。
#include<bits/stdc++.h> using namespace std; int main(void) { int m = 0; cout << m++ << endl; cout << m << endl; cout << endl; m = 0; cout << ++m << endl; cout << m << endl; cout << endl; m = 0; int num[3] = {0,0,0}; num[m++] = 1234; for(int i = 0;i < 3;++i) cout << num[i] << " "; cout << endl; m = 0; for(int i = 0;i < 3;++i) num[i] = 0; num[++m] = 1234; for(int i = 0;i < 3;++i) cout << num[i] << " "; cout << endl; return 0; }有错误，或者不懂的可以在评论区提出。