离散化

​ 离散化其实很简单，就是将我们很大范围的数字映射到一个相对于说较小的范围。其中分为不注重大小关系的离散化和注重元素大小位置的离散化。前面的很简单我们可以直接用拉链法来进行离散化就好。但是对于后者，我们需要先进行一个排序，排序之后还要去重，最后根据排序的下标进行离散化。这样相对麻烦。

​ 于是，就有了一个较简单的离散化方法，我先掏出结论！

1
2
3
4
5
6
7
8
9
10
11
//离散化a数组
public static void work(int[] a){
    for(int i = 1;i <= n;i++) p[i] = i;
    Arrays.sort(p,1,n+1.new Comparator<Integer>(){
        @Override
        public int compare(Integer o1,Integer o2){
            return a[o1] - a[o2];
        }
    });
    for(int i = 1;i <= n;i++) a[p[i]] = i;
}

​ 这个算法首先用p数组记录下a数组对应的每个下标（其实就是记录一下a原数组每个数字的位置），接着对p进行排序，排序依据是p数组对应的a数组里面的数字，其实这一步的意义就是计算出a数组排序后原来每个下标的位置在哪里。然后从小到大，也就是p[1] - p[n]（这里面存的是对应a数组原来位置）1-n的赋值。但是需要注意这个离散化之前需要数组去重！