经典算法：离散化的两种实现方式

思路一：下标映射

如果将下标也一同排序，数据将是怎么的形式呢？

将下标和元素绑定后，有一个好处，对应每个元素能 O(1) 的找出该元素在原始数组中的位置。

因此，我们只需要顺序遍历排序后的元素，顺序的将原数组的值改为[0, n-1]的映射即可。

具体的我们可以如下操作：

• 排序后的第 0 号元素 ---> 获取原数组 index1 ---> 将原数组的 1 号元素修改为 0
• 排序后的第 1 号元素 ---> 获取原数组 index4 ---> 将原数组的 4 号元素修改为 1
• 排序后的第 2 号元素 ---> 获取原数组 index2 ---> 将原数组的 2 号元素修改为 2
• 排序后的第 3 号元素 ---> 获取原数组 index3 ---> 将原数组的 3 号元素修改为 3
• 排序后的第 4 号元素 ---> 获取原数组 index0 ---> 将原数组的 0 号元素修改为 4

思路二：二分

其实这里的二分法回归本源也是基于下标映射的原理，只是实现是借助二分的形式。

在排序好的数组中对目标数值进行二分搜索，在O(logn)的时间复杂度内找到该数值是整体数据中的第几个。

具体的我们可以如下操作：

• 数值 10 ---> 二分搜索 10 ---> 有序序列中第 4 位置
• 数值 3 ---> 二分搜索 3 ---> 有序序列中第 0 位置
• 数值 8 ---> 二分搜索 8 ---> 有序序列中第 9 位置
• 数值 9 ---> 二分搜索 9 ---> 有序序列中第 3 位置
• 数值 4 ---> 二分搜索 4 ---> 有序序列中第 1 位置