题目

问题描述

离散化就是把无限空间（或非常大的空间）中有限的个体映射到有限的空间（较小空间）中去，以此提高算法的时空效率。通俗的说，离散化就是在不改变数据相对大小的条件下，对数据进行相应的缩小。

####栗子

原始数据：

1
8 999 91 100000 0000 15 999 91

离散化后：

1
1 3 4 2 3

离散化有什么用处呢？有时候我们需要根据数值的大小开一个数组，由于数值很多，没办法开那么大的数组（大了会超内存限制的），但是数据的个数有限。

如：有500000个数字，他们的范围是0-2000000000，这样就满足离散化的条件。我们可以把这些数离散化，最小的缩小为1，大小相邻的依次增加1，这样所有的数的范围一定能缩小到1到500000之间，同时不改变相对大小关系。

####任务

给你n个整数序列a[1],a[2],..,a[n]。请你在不改变相对大小关系的前提下进行离散化。

####要求

1.离散化后，最小的数值为1。
2.原序列中相同的数，离散后还应相同。
3.大小相邻的两个数离散后相差为1。
4.离散后序列相对位置不变。

###输入

第一行n 原始数据的个数 。第二行n 个用一个空格隔开的整数 。

###输出

一行原序列离散后相应的序列 ，相邻两个数之间一个空格隔开。

###输入输出样例

discretize.in discretize.out
8 99991 1000000000 15 99991 1 3 4 2 3

###数据范围

30%的数据： n<100, 0< a[i]<1000;

100% 的数据： n<500000 0< a[i]<2000000000

第一种方法

思路

其实就是用一个辅助的数组把你要离散的所有数据存下来。

然后排序，排序是为了后面的二分。

去重，因为我们要保证相同的元素离散化后数字相同。

再用二分把离散化后的数字放回原数组。

注意事项

1.去重并不是把数组中的元素删去，而是重复的部分元素在数组末尾，去重之后数组的大小要减一

2.二分的时候，注意二分的区间范围，一定是离散化后的区间

3.如果需要多个数组同时离散化，那就把这些数组中的数都用数组存下来

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//n:原数组大小
//num:原数组中的元素
//lsh:离散化的数组
//cnt:离散化后的数组大小 
int lsh[MAXN] , cnt , num[MAXN] , n;
for(int i=1; i<=n; i++)
{
    scanf("%d",&num[i]);
    lsh[i] = num[i];    
}
sort(lsh+1 , lsh+n+1);
cnt = unique(lsh+1 , lsh+n+1) - lsh - 1;
for(int i=1; i<=n; i++)
    num[i] = lower_bound(lsh+1 , lsh+cnt+1 , num[i]) - lsh;

第二种方法

思路

其实就是排序之后，枚举着放回原数组

用一个结构体存下原数和位置，按照原数排序

我结构体里面写了个重载，也可以写一个比较函数

最后离散化后数在rank[]里面

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
struct Node
{
    int data, id;
    bool operator < (const Node& a) const
    {
        return data < a.data;
    }
};
Node num[MAXN];
int rank[MAXN], n;
for (int i = 1; i <= n; i++)
{
    scanf("%d", &num[i].data);
    num[i].id = i;
}
sort(num + 1, num + n + 1);
for (int i = 1; i <= n; i++)
{
    rank[num[i].id] = i;
}