就地数组重新排序? [英] 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屋！