网上做一道题2元的网站,聊城网站建设 推广聊城博达,涿州李战彪,学做网站培训 上海目录 1. 问题背景2. 解决方案 1. 问题背景
给定一个乱序数组#xff1a;
[7, 8, 1, 5, 3, 4, 2, 0, 9, 6]将其从小到大排序后可以得到#xff1a;
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]从乱序到有序只需要调用一下 sort 函数#xff0c;但要从有序恢复至原先的乱序又该如何做呢… 目录 1. 问题背景2. 解决方案 1. 问题背景
给定一个乱序数组
[7, 8, 1, 5, 3, 4, 2, 0, 9, 6]将其从小到大排序后可以得到
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]从乱序到有序只需要调用一下 sort 函数但要从有序恢复至原先的乱序又该如何做呢
2. 解决方案
我们可以在排序的时候记录下索引的变化。起初
Array: [7, 8, 1, 5, 3, 4, 2, 0, 9, 6]
Index: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]排序后
Array: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
Index: [7, 2, 6, 4, 5, 3, 9, 0, 1, 8]根据 Index 的变化可以建立如下的映射 7 → 0 2 → 1 6 → 2 4 → 3 5 → 4 3 → 5 9 → 6 0 → 7 1 → 8 8 → 9 7\to 0 \\ 2\to 1 \\ 6\to 2 \\ 4\to 3 \\ 5\to 4 \\ 3\to 5 \\ 9\to 6 \\ 0\to 7 \\ 1\to 8 \\ 8\to 9 \\ 7→02→16→24→35→43→59→60→71→88→9
排序的过程可以认为是把箭头左边对应位置上的数字移动到箭头右边对应的位置上例如 6 → 2 6\to2 6→2 代表把第6个位置上的数字移动到第2个位置上。若要恢复原先的乱序就要把第2个位置上的数字移动到第6个位置上。假设恢复前的数组为 _res恢复后的数组为 res那么不难看出有 res[6] _res[2]。
如何获得上面的映射呢首先我们可以获得排序后的 Index 数组然后根据这个数组建立一个逆映射
import randomrandom.seed(0)
a list(range(10))
random.shuffle(a)
print(Array:, a)
# Array: [7, 8, 1, 5, 3, 4, 2, 0, 9, 6]b sorted(enumerate(a), keylambda x: x[1])
idx_map, sorted_a zip(*b)
print(idx_map)
# (7, 2, 6, 4, 5, 3, 9, 0, 1, 8)inverse_idx_map {j: i for i, j in enumerate(idx_map)}恢复原先的乱序数组只需要新开一个数组然后遍历这个逆映射即可
c [None] * 10
for k, v in inverse_idx_map.items():c[k] sorted_a[v]
print(c)
# [7, 8, 1, 5, 3, 4, 2, 0, 9, 6]有一个问题是空间复杂度一定是 O ( n ) O(n) O(n) 吗可不可以降到 O ( 1 ) O(1) O(1)答案是不可以。假设在某一步执行了 _res[k] _res[v]那么位于 k 处的元素就会被彻底覆盖掉无法再恢复。
据此可以总结整个算法流程
首先算出排序后的索引到排序前的索引映射 inverse_idx_map。遍历这个映射执行 res[k] _res[v]其中 _res 是恢复前的数组res 是恢复后的数组。
模版
def get_inverse_idx_map(arr, sort_func):idx_map, sorted_arr zip(*sorted(enumerate(arr), keysort_func))inverse_idx_map {j: i for i, j in enumerate(idx_map)}return inverse_idx_map, sorted_arrdef restore_arr(inverse_idx_map, sorted_arr):restored_arr [None] * len(sorted_arr)for k, v in inverse_idx_map.items():restored_arr[k] sorted_arr[v]return restored_arr
