本笔记内容来源于算法基础课

离散化

整数保序离散化

基本知识

对于个数特别少，值域特别大的数组a

将a映射到从0开始连续的自然数

这样的过程称为离散化

注意离散化后，数之间的绝对关系发生了改变，但相对关系没有发生改变

问题

1. 原数组中具有重复元素 $\rightarrow$ 去重
2. 如何快速地求出x离散化的值 $\rightarrow$ 二分

模板

将原数组映射为连续的下标
l为从0开始，l + 1 为从1开始

java模板

// 去重 --> 排序+双指针
Collections.sort(alls);
int j = 0;
for (int i = 0; i < alls.size(); i++) {
    if (i == 0 || alls.get(i) != alls.get(i - 1)) 
        alls.set(j++, alls.get(i));
}
int len = alls.size() - j;
for (int i = 0; i < len; i++) alls.remove(alls.size() - 1);
// alls = alls.subList(0, j);

// 二分
public static int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        if (alls.get(mid) >= x) r = mid;
        else l = mid + 1;
    }
    return l + 1;
}