我们思考一个问题:如果将下标也一同排序,数据将是怎么的形式呢?
将下标和元素绑定后,有一个好处,对应每个元素能 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
好了,今天的文章分享就到这里了,希望对大家的学习有帮助哦!