java - 使用更少的内存需要重新排序数组元素

Question

我最近有一个面试问题，以最少的内存使用对数组中的元素进行重新排序。不要使用任何额外的变量或集合等。

输入：

value   65 7 1 68 90
index    0 1 2  3  4

输出：

value   90 68 1 7 65
index    0  1 2 3  4

Answer 1

您可以使用XOR在元素之间交换（第一个与最后一个，第二个与最后一个等），如下所示：

int [] arr = {65, 7, 1, 68, 90};
for(int i=0; i<arr.length/2; i++){
    // the following 3 lines swap between elements arr[i] and arr[arr.length-i-1]
    arr[i] = arr[i] ^ arr[arr.length-i-1];
    arr[arr.length-i-1] = arr[i] ^ arr[arr.length-i-1];
    arr[i] = arr[i] ^ arr[arr.length-i-1];
}

for(int i=0; i<arr.length; i++){
    System.out.print(arr[i]+" ");
}

输出

90 68 1 7 65 

Answer 2

这里的主要问题是在不使用临时变量的情况下交换数组元素。您可以使用XOR(^)这样的操作：

对于交换a和b：

int a = 4;
int b = 5;
a ^= b
b ^= a
a ^= b

现在，您只需要从 to 遍历数组index = 0，index = length / 2并在开头和结尾交换元素。

Answer 3

看起来元素只是颠倒了。您可以在不使用其他数组的情况下执行此操作，使用您喜欢使用的任何交换实现：

int b = 0, e = array.length-1;
while (b < e) {
    array.swap(b, e);
    b = b + 1;
    e = e - 1;
}

对于整数，您可以通过计算总和和减法、异或等来使用“无存储交换”。不过，在生产中永远不会这样做——这是在硬件工程师兼任程序员的时候发明的一种无用的面试技巧。现在就做（大约 25 年前，我看到这个问题是用硬件逻辑门来表述的）。