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