就地阵列重新排序? [英] In-place array reordering?
本文介绍了就地阵列重新排序?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
比方说,我有一个数组 A
长度 N
和第二阵列指数
,也长 N
。 指数
包含了一些任意的排列顺序 [0,N)
。我想重新排列 A
这样的,它是由指数
指定的顺序。例如,用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)的时间,preferably没有突变指标完成
?
推荐答案
通过变异指数
:(。如果没有看起来很难(见稳定就地合并排序)。
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屋!
查看全文