前言

离散化算法

算法概要

离散化其实是一种数据处理的技巧，本质上可以看成是一种哈希运算，它保证数据在哈希运算以后仍然保持原来的全/偏序关系。

用来离散化的可以是整数、浮点数、字符串等等。

比如，首先给定一个序列，由于这个序列的范围很大，值域可能是 [0, 10^9]，但序列中的元素个数很少，个数可能只有 [0, 10^5]，有时候我们需要利用这些值作为数组下标，显然我们不可能去开辟一个 10^9 大小的数组，因此，我们需要将这个序列里面的数映射到一个从 0 开始的连续自然数。

其次，序列中存在负数也是同样的情况。

这里映射的过程就是离散化处理的过程，也可以称为哈希运算的过程。

其中需要注意的问题有：

• 原始序列中的元素可能是 重复 的，这就涉及到 去重。
• 如何快速算出 x（x 表示原始序列中的数值）离散后新的数组的下标值，可以用 二分查找 实现。

我们举个例子，对于数组 nums = [5, 6, 100, 100, 1000, 10000, 3, 4, 2, 2, 3]，可以看到它的值域远比数组长度要大。

所以我们对这个数组进行离散化处理，

• 首先排序并去重，得到 sort = [2, 3, 4, 5, 6, 100, 1000, 10000, 100, 1000, 10000]（下标从 1 开始），并且需要返回有效的数据个数，也就是 8。
• 如果将原始数组 nums 通过在 sort 上二分得到排名的方式来离散化，就可以将 nums 变为 [4, 5, 6, 6, 7, 8, 2, 3, 1, 1, 2]，这是不是就将原始数组离散化了，值域直接从 10000 降到 8，并且也没有改变原来的全/偏序关系。

实现

将一个数组离散化，并进行查询是比较常用的应用场景，通常原数组中会有重复的元素，一般把相同的元素离散化为相同的数据。

所以我们首先对原数组排序、去重并返回有效元素个数，即 size，进而得出有效的范围是 [0, size - 1]。

后续当需要查找离散化之后的值时，只需要基于原数组，进行二分搜索查找即可。

public int discretization(int[] nums) {
    Arrays.sort(nums);
    int n = nums.length;
    int sz = 1; // 右边界
    for (int i = 0; i < n; i++) {
        if (nums[sz - 1] != nums[i]) {
            nums[sz++] = nums[i];
        }
    }
    return sz;
}

public int find(int[] nums, int sz, int x) {
    int i = 0, j = sz - 1, m;
    while (i <= j) {
        m = i + j >> 1;
        if (nums[m] < x) {
            i = m + 1;
        } else if (nums[m] > x) {
            j = m - 1;
        } else {
            return m;
        }
    }
    return -1;
}

当然还有另一种基于 HashMap 和 TreeMap 的实现方式，首先 TreeMap 可以起到排序 + 去重的作用，其实使用 HashMap 记录每个元素的排名，或者说 HashMap 的 value 就是 key 离散化之后的值。

public Map<Integer, Integer> discretization(int[] nums) {
    Set<Integer> set = new TreeSet<>();
    for (int x : nums) {
        set.add(x);
    }
    // x -> rank
    Map<Integer, Integer> values = new HashMap<>();
    int idx = 0;
    for (int x : set) {
        values.put(x, idx++);
    }
    return values;
}