1

奇数と偶数が同数の配列があります。番号は順不同で保存されます。O(1)偶数が偶数インデックスに、奇数が奇数インデックスに送られるように、配列をインプレース (追加スペース) でシャッフルすることは可能ですか?

もちろん、補助記憶装置を使用して実装するのは簡単ですが、補助記憶装置を使用しないという制約により、それは難しくなります。[a1,a2,a3..an,b1,b2...bn...n1,n2,n3...nn]さらに、パターンはありません。配列をにシャッフルするような問題[a1,b1,c1..n1,a2,b2,c2...n2,...an,bn...nn]では、それを可能にする固定マッピングがあります。しかし、ここにはそのようなパターンはありません。

4

2 に答える 2

2

Write two iterators. One iterates all array indices of odd numbers at even positions. The other iterates all even numbers at odd positions.

Iterate over both simultaneously, and swap the items pointed to by the iterators until the end of the array. Should have O(n) performance.

于 2012-10-14T21:18:52.567 に答える
1

奇数用と偶数用の 2 つのインデックスを保持し、常に奇数/偶数の内容を持つ最初の偶数/奇数インデックスを見つけてから、スワップします。

int even = 0, odd = 1;
do {
    while(even < size && array[even] % 2 == 0) even += 2;
    while(odd < size && array[odd] % 2 == 1) odd += 2;
    if (even < size && odd < size) {
        int temp = array[even];
        array[even] = array[odd];
        array[odd] = temp;
    }
}while(even < size && odd < size);
于 2012-10-14T21:21:28.760 に答える