以给定顺序排列数组，而不复制数组或更改顺序

Question

我已经找到了几乎相同的问题。但是我需要做些复杂。

所以这是问题所在。您有一个包含元素的数组，另一个数组具有第一个数组的元素应遵循的特定顺序。这是一个示例：

int[] a = {5, 35, 7, 2, 7};
int[] order = {3, 0, 2, 4, 1};

算法后，a应该看起来像这样：

a = {2, 5, 7, 7, 35};

不能以任何方式更改命名为order的数组，并且禁止数组的所有副本。仅允许使用常量（如普通整数）。

请注意，此问题不是基于特定的语言。它应采用类似伪代码的语言。可以理解。

所以这里有人有想法吗？我在这个问题面前坐了3天，希望得到一些帮助，因为我认为我现在真的很困。

谢谢你。

Answer 1

order定义的排列由一个或多个周期组成。将一个循环应用于数组a很简单，但是面临的挑战是要以某种方式知道哪些数组元素属于您已经以这种方式处理过的循环。如果有一种方法可以像往常一样用mark访问元素，那么该问题就可以解决。但是，使用额外的位可以掩盖具有其他数据的阵列。因此必须排除。

[如果不存在执行此类标记的可能性，那么还有一条出路：仅当您位于该循环的最左索引（或最右）时，才对数组a执行循环操作。不利的一面是，在每个索引上，您都需要经历该索引所属的周期，以检查您是否确实处于其左侧极限。这意味着您将在同一个循环中循环几次。

这是JavaScript的外观：

function isLeftOfCycle(order, i) {
    let j = order[i]; 
    while (j > i) {
        j = order[j];
    }
    return (j === i); // a boolean
}

function applyCycle(arr, order, i) {
    let temp = arr[i];
    let k = i;
    let j = order[i];
    while (j > i) {
        arr[k] = arr[j];
        k = j;
        j = order[j];
    }
    arr[k] = temp;
}

function sort(a, order) {
    for (let i = 0; i < order.length; i++) {
        if (isLeftOfCycle(order, i)) {
            applyCycle(a, order, i);
        }
    }
}

// Example run:
let a = [5, 35, 7, 2, 7];
let order = [3, 0, 2, 4, 1];
sort(a, order);
console.log(a);

显然，这是有代价的：时间复杂度不再是O（n），而是O（n²）。

Answer 2

给出您可以显示的数字范围：

• 将对应订单值的100倍添加到a的每个项目中。
• 排序a。
• 替换逐项取模100的每一项。

某些Python：

a = [5, 35, 7, 2, 7]
order = [3, 0, 2, 4, 1]

mult = max(a) + 1
a = [a_item + order_item * mult
     for a_item, order_item in zip(a, order)]
a.sort(reverse=True)
a = [a_item % mult for a_item in a]

print(a)    # [2, 5, 7, 7, 35]

我应该强调，它适用于所示的数字；负面因素和溢出注意事项可能会限制更广泛的适用性。