就地数组重新排序? [英] In-place array reordering?
本文介绍了就地数组重新排序?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
假设我有一个长度为 n
的数组 a
和一个长度为 n
的第二个数组 indices
>.indices
包含序列 [0, n)
的一些任意排列.我想重新排列 a
,使其按照 indices
指定的顺序排列.例如,使用 D 语法:
Let's say I have an array a
of length n
and a second array indices
, also of length n
. indices
contains some arbitrary permutation of the sequence [0, n)
. I want to to rearrange a
such that it's in the order specified by indices
. For example, using D syntax:
auto a = [8, 6, 7, 5, 3, 0, 9];
auto indices = [3, 6, 2, 4, 0, 1, 5];
reindexInPlace(a, indices);
assert(a == [5, 9, 7, 3, 8, 6, 0]);
这是否可以在 O(1) 空间和 O(n) 时间内完成,最好不要改变索引
?
Can this be done in both O(1) space and O(n) time, preferably without mutating indices
?
推荐答案
With mutating indices
:(.没有看起来很难(参见 stable in-place mergesort).
With mutating indices
:(. Without looks hard (see stable in-place mergesort).
a = [8, 6, 7, 5, 3, 0, 9]
indices = [3, 6, 2, 4, 0, 1, 5]
for i in xrange(len(a)):
x = a[i]
j = i
while True:
k = indices[j]
indices[j] = j
if k == i:
break
a[j] = a[k]
j = k
a[j] = x
print a
这篇关于就地数组重新排序?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文