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(最初と最後、2 番目と最後から 2 番目など)。

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

ここで、配列を から まで反復処理し、最初と最後で要素を交換するだけ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;
}

整数の場合、合計を計算して減算する、XOR 演算などを行うことにより、「storageless swap」を使用できます。ただし、本番環境では決してこれを行うことはありません。これは、ハードウェア エンジニアが自分よりも頻繁にプログラマーを兼ねていたときに発明された、インタビューで使われる無駄なトリックです。 (私は、この問題がハードウェアの論理ゲートの観点から定式化されたのを 25 年前に見ました)。