Algorithm22 数据结构 离散化
[TOC]
数据结构 离散化
本质：是一种哈希，将原数组进行哈希映射，映射前后仍然保持全序/偏序
过程：排序->去重->索引（对应到stl中就是首先sort排序->然后unique去重->最后lowerbound二分找位置作为索引）
demo1：
1,23424,21472313246768,6594,95,0,65535313=>1,4,6,3,2,0,5demo2：
32434234，32434234，43324556，8384733，98998988=>0,0,1,2,3demo3（存在需要去重的情况=>这种情况下是需要将重复的元素离散化为相同索引，然后起后面的索引依次往前递补）：
0, 1,23424,1,0,20746768,6594,95,0,6553513=>1,4,1,0,6,3,2,0,5
数组实现
三个数组：a[maxn] b[maxn] c[maxn]，分别是原串、原串经排序之后的串、离散化之后的串
三个过程：排序、去重、索引
三个算法实现对应过程：sort排序、unique去重并获取
#include <iostream>
using namespace std;
const int maxn = 1e3+9;
#include <algorithm>
//int n = 7, a[maxn] = {0, 1,23424,20746768,6594,95,0,6553513}, b[maxn], c[maxn];
// 原串 a={1,23424,20746768,6594,95,0,6553513}
// 中间串 b={0,1,95,6594,23424,6553513,20746768}
// 离散化 c={1,4,6,3,2,0,5}
int n = 9, a[maxn] = {0, 1,23424,1,0,20746768,6594,95,0,6553513}, b[maxn], c[maxn];
// 原串 a={1,23424,1,0,20746768,6594,95,0,6553513}
// 中间串 b={0,1,95,6594,23424,6553513,20746768,6553513,20746768}
// 离散化 c={1,4,1,0,6,3,2,0,5}
int main() {
for (int i = 1; i <= n; ++i) b[i] = c[i] = a[i];
// 排序
sort(b+1, b+1+n);
// 去重
int size = unique(b+1, b+1+n)-b-1;
// 索引
for (int i = 1; i <= n; ++i) c[i] = lower_bound(b+1, b+1+size, a[i])-b-1;
cout<<"原串 ";for (int i = 1; i <= n; ++i) printf("%d ", a[i]);
cout<<"\n中间排序串 ";for (int i = 1; i <= n; ++i) printf("%d ", b[i]);
cout<<"\n离散化串 ";for (int i = 1; i <= n; ++i) printf("%d ", c[i]);
return 0;
}
结构体实现
数据结构：构造结构体，重载运算符（val和idx一次排序）。
1、根据val来排序，如果val相同的话，就根据idx索引递增的次序
2、再将每个位置反向赋值回去。
struct DisNum {
int idx, val;
bool operator < (const DisNum n) const {
if (val == n.val) return idx < n.idx;
return val < n.val;
}
}a[maxn];
赋值，排序，然后再反向赋值回去
for (int i = 1; i <= n; ++i) {scanf("%d", &a[i].val);a[i].idx = i;}
sort(a+1, a+1+n);
for (int i = 1; i <= n; ++i) nw[a[i].idx] = i;