0sとsの混合物を含む配列があり1ます。sとsの数は変わらないという制約の下で、配列内の偶数の位置にできるだけ多く含まれ0、奇数の位置にできるだけ多く含まれるように、配列の内容を再配置したいと思います。これは、sの数がsの数を超える場合、またはその逆の場合、再配置された配列の最後に、すべてまたはすべてで構成されるブロックが存在することを意味します。アレイを所定の位置に変更して、これを1回のパスで行うにはどうすればよいですか？1010101
例えば：
Input: {0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1}
Output: {0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1}
これには、標準の2色ソートアルゴリズムを使用できます。配列参照を編集して、配列の前半へのアクセスを実際の配列の偶数要素にマップし、配列の後半へのアクセスを実際の配列の奇数要素に（逆方向に）マップします。基本的に、次のようにa[i]なります（偶数であると仮定size）：
a[i < size/2 ? i * 2 : (size - i) * 2 - 1]
int a[10] = {1, 1, 0, 1, 1, 0, 1, 1, 1, 0};
int i;
int count_0 = 0;
int count_1 = 0;
for(i = 0; i < 10; i++)
{
if(a[i] == 0)
{
if(count_1 > 0)
{
if(i % 2 == 0)
{
a[i-2*count_1+1] = 0;
a[i] = 1;
count_1--;
}
else
{
a[i-2*count_1] = 0;
a[i] = 1;
}
}
else
{
if(i % 2 == 0)
count_0++;
}
}
else
{
if(count_0 > 0)
{
if(i % 2 != 0)
{
a[i-2*count_0+1] = 1;
a[i] = 0;
count_0--;
}
else
{
a[i-2*count_0] = 1;
a[i] = 0;
}
}
else
{
if(i % 2 != 0)
count_1++;
}
}
}
「それらをそのままにしておく」が「どこに行き着くかは問題ではない」という意味でない限り、1回のパスで作成できるとは思いません。
これが2つのパスでの私の試みです:)
void zeroone(int *arr, size_t n) {
int *ptr = arr;
size_t nn = n;
int s = 0;
/* if the array has an odd number of elements
** the number of 0's is different then the number of 1's */
if (n % 2) return;
/* 1st pass */
while (nn--) s += *ptr++;
/* if there are as many 0's as 1's */
if (s+s == n) {
/* 2nd pass */
for (nn = 0; nn < n; nn += 2) {
arr[nn] = 0;
arr[nn + 1] = 1;
}
}
}
これはシングルパスで実行できます。
シングルパスを使用する別のソリューションを次に示します。アイデアは、2つのインデックスpos_0を保持することであり、これは、配列内の次のまたは配置されるpos_1場所を保持します。配列をトラバースするために使用されます。01i
//
//array a[] and length are members of the class AlternateZeroAndOne
//
void AlternateZeroAndOne::sortArray()
{
int pos_0 = 0;
int pos_1 = 1;
for (int i=0; i<length; ++i)
{
//
// We have been waiting for a zero to be placed at the correct location.
//
if (pos_0 < pos_1)
{
if (a[i] == 0)
{
swap(pos_0, i);
pos_0+=2;
//
// If we had a 1 already at the right place, increment pos_1.
//
if (a[pos_1] == 1)
pos_1+=2;
}
}
//
// We have been waiting for a one to be placed at the correct location.
//
else
{
if (a[i] == 1)
{
swap(pos_1, i);
pos_1 += 2;
//
// If we had a 0 already at the right place, increment pos_0.
//
if (a[pos_0] == 0)
pos_0+=2;
}
}
}
}
#include<iostream>
using namespace std;
//////////////////////////////////////////
int a[]={1,1,0,1,0,1,1,1,0,1,0,1,0,0,0,0,1,1,1,1,0,0} ;
int main()
{
int zero = 0, one = 1;
int n = sizeof(a)/sizeof(*a);
int i = 0;
while ( zero < n && one < n)
{
if(a[zero] != 0 && a[one] != 1)
{
swap(a[zero],a[one]);
}
if(a[zero] == 0)
{
zero=zero+2;
}
if(a[one] == 1)
{
one=one+2;
}
}
}
これでできます。結果は提案された出力とは異なりますが、指定されたルールと同じです (問題のテキストには「並べ替え」という単語が含まれていません0。1それらを「圧縮」する必要はありません)。「圧縮」するのはもう少し複雑です。
static void Main(string[] args)
{
var input = new[] { 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1 };
var lastEvenToMove = -1;
var lastOddToMove = -1;
for (int i = 0; i < input.Length; i++)
{
bool needEven = i % 2 == 0;
bool isEven = input[i] == 0;
if (needEven == isEven)
{
continue;
}
if (needEven)
{
if (lastEvenToMove != -1)
{
var old = input[lastEvenToMove];
input[lastEvenToMove] = 1;
input[i] = 0;
lastEvenToMove = old;
}
else
{
input[i] = lastOddToMove;
lastOddToMove = i;
}
}
else
{
if (lastOddToMove != -1)
{
var old = input[lastOddToMove];
input[lastOddToMove] = 0;
input[i] = 1;
lastOddToMove = old;
}
else
{
input[i] = lastEvenToMove;
lastEvenToMove = i;
}
}
}
while (lastEvenToMove != -1)
{
var old = input[lastEvenToMove];
input[lastEvenToMove] = 0;
lastEvenToMove = old;
}
while (lastOddToMove != -1)
{
var old = input[lastOddToMove];
input[lastOddToMove] = 1;
lastOddToMove = old;
}
Console.WriteLine(@"{{{0}}}", String.Join(", ", input.Select(p => p.ToString())));
}
オッズのスタックと移動が必要な偶数の要素のスタックを保持し、奇数/偶数が必要なときにこれらを使用します。2 つのスタックは入力配列に保持されるため、余分なスペースはありません (2 つのスタックの 2 つの「先頭」、つまり 2 つの余分な整数を除く)。O(1.5n)最悪のケースは、時間 (たとえば、すべての要素が1であり、要素の半分がスタックに「置かれ」、空きスペースがなかったためにリセットする必要がある) とスペースのためだと思いますO(1)。
出力：
{0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1}
1 と 0 しかないので、それらの量の差を数えるだけで、並べ替えは非常に簡単になります。
int size = arr.length();
int diff = 0, i;
for(i = 0; i < size; i++) // put 0 in odd places and 1 in even and count the extra changes
if(i % 2 == 0)
if(arr[i] == 1){
arr[i] = 0;
diff++;
}
else
if(arr[i] == 0){
arr[i] = 1;
diff--;
}
for(i--; diff != 0; i--){ //make the tail
if(diff > 0) //if we owe 1's put in on 0's
if(arr[i] == 0){
arr[i] = 1;
diff--;
}
if(diff < 0) //if we owe 0's put in on 1's
if(arr[i] == 1){
arr[i] = 0;
diff++;
}
}
なぜそれが正しいのかは簡単にわかるので、説明しません。時間計算量: O( arr.length() ) または O(n)
#include<stdio.h>
void swap(int *p,int *q)
{
int temp=*p;
*p=*q;
*q=temp;
}
int main()
{
int a[]={0,1,1,0,1,0,1,0,1,1,1,0,0,1,0,1,1};
int z=0,o=1,i;
while(z<17&&o<17)
{
if(a[z]==1&&a[o]==0)
swap(&a[z],&a[o]);
if(a[z]==0)
z+=2;
if(a[o]==1)
o+=2;
}
if(z<17&&a[z]==1)
{
while(z<15)
{
swap(&a[z],&a[z+2]);
z+=2;
}
}
if(o<17&&a[o]==0)
{
while(o<15)
{
swap(&a[o],&a[o+2]);
o+=2;
}
}
for(i=0;i<17;i++)
printf("%d ",a[i]);
}