离散化

发表于 更新于 分类于 ，
本文字数： 614

关于离散化算法的理解

给定一个值域(1e9)很大，个数不多(1e5)的数列 如何以这些值为下标来实现某些算法呢？
可以将这些数排序后映射到从0或1开始的自然数 称为 离散化
实现离散化有两个关键步骤：

  1. 这些数字中有重复需要 去重 
    1
    2
    3
    sort(a.begin(), a.end());

    a.erase(unique(a.begin(), a.end()), a.end());
    这里unique实现的操作是将a容器中的重复元素放置于容器的后面，并且返回去重后容器的尾端点
    代码实现unique（没有实现放置重复元素于后的功能）（双指针）：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    vector<int>::iterator unique(vector<int> &a)
    {
        int j = 0;
        for (int i = 0; i < a.size(); i++)
        {
            if (!i  a[i] != a[i - 1])
                a[j++] = a[i];
        }
        return a.begin() + j;
    }
  2. 如何快速求出这些数字离散化后映射的数字  （使用二分）
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    int find(int x)
    {
        int l = 0, r = a.size() - 1;
        while (l < r)
        {
            int mid = (l + r) / 2;
            if (a[mid] >= x)
                r = mid;
            else
                l = mid + 1;
        }
        return r;
    }//映射到从0开始的自然数