有时候会碰到一些问题给的数不多，但是值很大，比如给五个数，1274,2491294,28742,1882,1，这五个数很分散，在树状数组中，如果用这几个数的值作为下标的话，那就相当浪费了，而且数据要是太大（或者出现负数），下标甚至还会存不下
这个时候如果我们把这五个数变成2,5,4,3,1，对应他们的相对大小关系，那么问题就好解决多了
我先写了个概念性的代码，基本没什么实际用途，毕竟Hash数组的下标存的还是原来的值，就给个大概的想法
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned long long ull; 5 #define inf 0x3f3f3f3f 6 const ll INF = 0x3f3f3f3f3f3f3f3f; 7 const ll MAXN = 1e6 + 7; 8 const ll MAXM = 1e3 + 7; 9 const ll MOD = 1e9 + 7; 10 const double eps = 1e-6; 11 const double pi = acos(-1.0); 12 int a[MAXN]; 13 int Hash[MAXN]; 14 int main() 15 { 16 int n; 17 while (cin >> n) 18 { 19 int cnt = 0; 20 for (int i = 0; i < n; i++) 21 cin >> a[i]; 22 sort(a, a + n); 23 for (int i = 0; i < n; i++) 24 Hash[a[i]] = i; 25 for(int i=0;i<n;i++) 26 printf("a[%d]=%d 在数组中第几小=%d\n",i,a[i],Hash[a[i]]+1); 27 } 28 return 0; 29 }
看懂了吧（我都懂了那大家肯定都懂了） 那么下面是两个比较常用的离散化方法
1:包含重复元素，相同元素离散化后也相同,在这种情况下推荐使用
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned long long ull; 5 #define inf 0x3f3f3f3f 6 const ll INF = 0x3f3f3f3f3f3f3f3f; 7 const ll MAXN = 1e5 + 7; 8 const ll MAXM = 1e3 + 7; 9 const ll MOD = 1e9 + 7; 10 const double eps = 1e-6; 11 const double pi = acos(-1.0); 12 int a[MAXN], t[MAXN], b[MAXN]; 13 //包含重复元素，并且相同元素离散化后相同 14 int main() 15 { 16 int n; 17 while (scanf("%d", &n)) 18 { 19 int cnt = 0; 20 for (int i = 1; i <= n; i++) 21 scanf("%d", &a[i]), t[i] = a[i]; 22 sort(t + 1, t + n + 1); 23 int m = unique(t + 1, t + 1 + n) - t - 1; //不重复元素个数 24 for (int i = 1; i <= n; i++) 25 b[i] = lower_bound(t + 1, t + 1 + m, a[i]) - t; 26 //a[i]为原来的数组,b[i]为离散化后的数组 27 for (int i = 1; i <= n; i++) 28 printf("b[%d]=%d\n", i, b[i]); 29 } 30 return 0; 31 }
有个要注意的地方 1 1 2 2 3 3 4 4 5 7 8 unque后是1 2 3 4 5 7 8 4 5 7 8，只改变了前七个数字，后面的四个数字不变（最好自己写个试试看）
2：复杂度低，1.包含重复元素，并且相同元素离散化后不相同，2.不包含重复元素，并且不同元素离散化后不同，符合这两种的其中一个，推荐使用
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 typedef unsigned long long ull; 5 #define inf 0x3f3f3f3f 6 const ll INF = 0x3f3f3f3f3f3f3f3f; 7 const ll MAXN = 1e5 + 7; 8 const ll MAXM = 1e3 + 7; 9 const ll MOD = 1e9 + 7; 10 const double eps = 1e-6; 11 const double pi = acos(-1.0); 12 struct Node 13 { 14 int data, id; 15 bool operator<(const Node &a) const 16 { 17 return data < a.data; 18 } 19 }; 20 Node num[MAXN]; 21 int b[MAXN], n; 22 /* 第二种方式其实就是排序之后，枚举着放回原数组 23 用一个结构体存下原数和位置，按照原数排序 24 结构体里面写个重载，也可以写一个比较函数 25 最后离散化后数在b数组里面*/ 26 int main() 27 { 28 while (~scanf("%d", &n)) 29 { 30 for (int i = 1; i <= n; i++) 31 { 32 scanf("%d", &num[i].data); 33 num[i].id = i; 34 } 35 sort(num + 1, num + n + 1); 36 for (int i = 1; i <= n; i++) 37 b[num[i].id] = i; 38 for (int i = 1; i <= n; i++) 39 printf("b[%d]=%d\n", i, b[i]); 40 } 41 return 0; 42 }
原文：https://www.cnblogs.com/graytido/p/10909002.html
