GabWiki

Appearance

离散化 ​

离散化是一种比较特殊的哈希方式。

详细介绍：离散化 - OI Wiki。

实例：【离散化, 前缀和】区间和「离散化经典应用」

C++ 模板 ​

C++
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重
vector<int> alls; // 存储所有待离散化的值
sort(alls.begin(), alls.end()); // 排序
alls.erase(unique(alls.begin(), alls.end()), alls.end()); // 去重

二分求出 x 对应的离散化的值：

C++
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        // 找到第一个大于等于x的位置
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    // 映射若从0开始直接返回 从1开始返回要+1
    return r + 1;
}
int find(int x) {
    int l = 0, r = alls.size() - 1;
    while (l < r) {
        int mid = l + r >> 1;
        // 找到第一个大于等于x的位置
        if (alls[mid] >= x) r = mid;
        else l = mid + 1;
    }
    // 映射若从0开始直接返回 从1开始返回要+1
    return r + 1;
}

Java 模板 ​

Java
List<Integer> alls = new ArrayList<>(); // 存储所有待离散化的值
Collections.sort(alls); // 排序
alls = alls.subList(0, unique()); // 去重
List<Integer> alls = new ArrayList<>(); // 存储所有待离散化的值
Collections.sort(alls); // 排序
alls = alls.subList(0, unique()); // 去重

unique() 函数实现： 实现原理见：【双指针】删除有序数组中的重复项

Java
int unique() {
    int n = alls.size();
    int slow = 0;
    for (int fast = 0; fast < n; ++fast) {
        // 注意这里拿到的是整数包装类 所以一定要使用equals()方法判断是否相同
        if (!alls.get(slow).equals(alls.get(fast))) alls.set(++slow, alls.get(fast));
    }
    return slow + 1;
}
int unique() {
    int n = alls.size();
    int slow = 0;
    for (int fast = 0; fast < n; ++fast) {
        // 注意这里拿到的是整数包装类 所以一定要使用equals()方法判断是否相同
        if (!alls.get(slow).equals(alls.get(fast))) alls.set(++slow, alls.get(fast));
    }
    return slow + 1;
}

二分求出 x 对应的离散化的值：

Java
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;
}
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;
}