离散化

简介

离散化（(discretization)）可以理解为一种哈希映射，把无限空间中有限的个体映射到有限的空间中去。

具体来说，离散化是在不改变数据相对大小的条件下，对数据进行相应的缩小。

如下述数据：

原数据     : 20, 9, 1000, 4009
离散化后数据: 2, 1, 3, 4

元组也是同理

原数据     : {29, 49}, {10, 119}, {114514, 2}
离散化后数据: {3, 4}, {2, 5}, {6, 1}

由于离散化需要获取所有的数据后进行判断大小，以此决定每个值的映射

所以离散化不是一个在线算法

在线算法：是指它可以以序列化的方式一个个的处理输入，也就是说在开始时并不需要已经知道所有的输入。

什么时候可以使用离散化

当数据只与它们之间的相对大小有关，而与具体是多少无关时，可以进行离散化。

实现

对于相同元素有两种情况：

1. 相同元素离散化后依然相同
2. 相同元素离散化后不相同（与原下标有关）

第二种情况的例子如下：

原数据: 9, 9, 8, 100
离散化: 2, 3, 1, 4

对于第二种情况，我们是不能将原数组去重的，因为相同元素之间是有大小关系的（此处的大小关系仅指大于与小于关系）

相同元素离散化后依然相同

实现思路：

1. 拷贝数据
2. 对拷贝数据进行排序
3. 对排序后的数据进行去重
4. 遍历原数组，对其数据在拷贝数组中二分查找下标

Java

对有序数组的去重可以通过双指针解决

(Java) 拷贝数组：System.arraycopy(原数组, 起始下标, 拷贝数组, 起始下标, 拷贝个数)

/**
 * 有序数组去重
 * @param nums 有效数据下标从0开始的数组
 * @param n    原数组长度
 * @return 去重后数组长度(尾下标+1)
 */
int adjacentRemove(int[] nums, int n) {
    int slow = 0;
    for (int fast = 1; fast < n; ++fast) {
        if (nums[slow] != nums[fast]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1;
}
/**
 * 离散化, 将原数据映射到0开始
 * @param nums 有效数据下标从0开始的数组
 * @return 离散化后的最大值+1
 */
int discrete(int[] nums) {
    int n = nums.length;
    int[] temp = new int[n];
    System.arraycopy(nums, 0, temp, 0, n);
    Arrays.sort(temp);
    int cnt = adjacentRemove(temp, n);
    // 下面部分可以删除
    // 可以不修改原数组, 当需要时再查找映射后的下标
    for (int i = 0; i < n; ++i) {
        nums[i] = Arrays.binarySearch(temp, 0, cnt, nums[i]);
    }
    return cnt;
}

C++

C++ (algorithm) 库中的 (unique) 实现了有序数组的去重

返回去重后的末尾迭代器 unique(起始迭代器, 末尾迭代器)

注意：(unique) 并不是直接删除重复元素，而是将重复元素移动至了尾部

template <typename T>
int discrete(std::vector<T>& arr) {
    std::vector<T> copy = arr;
    std::sort(copy.begin(), copy.end());
    auto end = std::unique(copy.begin(), copy.end());
    // 下面部分可以删除
    // 可以不修改原数组, 当需要时再查找映射后的下标
    for (auto&& v : arr) {
        v = std::lower_bound(copy.begin(), end, v) - copy.begin();
    }
    return end - copy.begin();
}

相同元素离散化后不相同

用处不大

实现思路：

1. 用一个元组，将其本来的数据和下标绑定
2. 对这个元组排序
3. 按照原来的 (id) 赋值（具体看代码部分）

Java

public class Main {
    public static void main(String[] args) throws IOException {
        int n = 10;
        Random rand = new Random();
        Pair[] discrete = new Pair[n];
        for (int i = 0; i < n; i++) {
            discrete[i].val = rand.nextInt();
            discrete[i].id = i;
        }
        Arrays.sort(discrete);
        int[] rank = new int[n];
        for (int i = 0; i < n; i++) {
            // 原来id位置的数映射到 i
            rank[discrete[i].id] = i;
        }
    }
}

class Pair implements Comparable<Pair> {
    int val, id;

    // 按照val升序排序
    @Override
    public int compareTo(Pair o) {
        if (val != o.val) return val - o.val;
        return id - o.id;
    }
}

C++

struct node {
    T val;
    int id;
    // 按照val升序排序
    bool operator<(const node& o) const {
        if (val != o.val) return val < o.val;
        return id < o.id;
    }
};
signed main() {
    int n = 10;
    std::vector<node<int>> discrete(n);
    for (int i = 0; i < n; ++i) {
        discrete[i].val = rand();
        discrete[i].id = i;
    }
    std::sort(discrete.begin(), discrete.end());
    std::vector<int> rank(n);
    for (int i = 0; i < n; ++i) {
        // 原来id位置的数映射到 i
        rank[discrete[i].id] = i;
    }
}