思路一下标映射如果将下标也一同排序数据将是怎么的形式呢将下标和元素绑定后有一个好处对应每个元素能 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 位置
