数组离散化

1 问题描述

  • 离散化一个序列的前提是我们只关心这个序列里面元素的相对大小，而不关心绝对大小（即只关心元素在序列中的排名）；离散化的目的是让原来分布零散的值聚集到一起，减少空间浪费。那么如何获得元素排名呢，我们可以对原序列排序后去重，对于每一个$a_i$通过二分查找的方式计算排名作为离散化之后的值。当然这里也可以不去重，不影响排名。
  • 数组本质上是一种有序的映射。i—-A—->x 即(A[i]=x)的映射。有时候为了建立值的数量与坐标i的反向映射，但此时值x的范围是离散化的。需要建立离散数组。一个的额外的映射数组，完成反向映射x—-B—->i。

2 离散数组——数组实现方法

  • 使用数组B作为离散数组的映射。B的下标i能够反映原来数组中各个元素的大小顺序。但不是原来数组中各个元素的值。
  • 建立离散数组的时间复杂度为O(nlog n)需要对原数组进行快速排序。

代码实现

1
2
3
4
5
6
7
8
9
10
vector<int> nums;//表示原来的数组
vector<int> tmp = nums;

//对离散数组进行排序
sort(tmp.begin(), tmp.end());

//建立原数组到离散数组的映射
for (int& num: nums) {
    num = lower_bound(tmp.begin(), tmp.end(), num) - tmp.begin() + 1;
}

3 离散数组——有序map实现方法

  • 有序map的创建，底层使用红黑树实现。本质上就是一种离散数组。根据键的大小进行了排序。
  • 可以使用这种有序的映射直接完成原数组的值到下表i的映射。并且保持一定的顺序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include<iostream>
#include<map>
using namespace std;


int main(){
    map<int,int> m;
    m[10]=10;
    m[4]=4;
    m[5]=5;
    m[1000]=1000;
    m[1]=1;
    for(auto k:m){
        cout<<k.first<<endl;
    }
    return 0;
}