我有一個包含0 s和1 s的混合物的陣列。我想重新排列數組的內容，以便數組中的偶數位置包含0，並且奇數位置儘可能包含1，但須遵守0s和1s的數量不變的限制。這意味着如果0 s的數量超過了1 s的數量，反之亦然，那麼在重新排列的數組的末尾會有一個塊，由全部0 s或全部1 s組成。我怎樣才能一次完成此操作，修改陣列？雙色抖動
例如：
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}
你可以使用這個標準的雙色排序算法;只需編輯數組引用即可將對數組前半部分的訪問映射到實際數組中的偶數元素，並將數組的後半部分訪問到實際數組中的奇數元素（向後）。基本上，a[i]變（假設size甚至）：
a[i < size/2 ? i * 2 : (size - i) * 2 - 1]
你能給我一個雙色排序算法的參考嗎？我還沒有發現它與谷歌。 – xanatos 2011-03-10 18:23:16
@xanatos：見http://en.wikipedia.org/wiki/Quicksort#Complex_version;在你的情況下，主鍵是1，你在開始的時候把事物放在比它小的地方，而事物大於或等於它的結尾。 – 2011-03-10 19:28:22
我不認爲它可以在1個行程進行，除非「離開他們，他們是」意味着「不，他們到底怎麼做向上」。
這是我嘗試用兩道:)
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;
}
}
}
+1同意。如果必須進行「排序」，直到第一遍結束才能確定，因此無法在第一次迭代中執行「排序」。在一次迭代中完成它的唯一方法是使用第二個數組。 – ruslik 2011-03-11 00:57:31
遍歷數組，維持3個變量的不變量和數組：
pos已排序。color是應放置在pos處的元素的顏色。pos和next之間的所有內容都具有相同的顏色。無論如何，它似乎工作。
def odd_even_sort(xs):
color = 0
pos = 0
next = pos + 1
while next < len(xs):
if xs[pos] == color:
pos += 1
if pos >= next:
next = pos + 1
color = not color
elif xs[next] == color:
xs[pos], xs[next] = xs[next], xs[pos]
next += 1
pos += 1
color = not color
else:
next += 1
xs = [0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1]
odd_even_sort(xs)
print xs
這樣做。結果與提出的輸出不同，但與給出的規則相同（問題的文本不包括「排序」一詞，只是在最後必須將所有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())));
}
我保持的可能性的堆疊和需要移動的偶數元件的堆疊，並且我使用這些當我需要奇數/偶數。這兩個堆棧保存在輸入數組中，所以沒有額外的空間（除了兩個堆棧中的兩個「頭」，即兩個額外的整數）。我認爲最糟糕的情況是時間爲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<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;
}
}
}
這可以單程完成。
這是另一種使用單程的解決方案。這個想法是保持兩個索引pos_0和pos_1，它們保存下一個0或1要放置在陣列中的位置。將使用i遍歷數組。
//
//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;
}
}
}
}
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++;
}
}
}
歡迎來到StackOverflow，儘管這段代碼看起來很有用，可以幫助別人理解它。 – 2012-12-12 11:54:20
#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]);
}
這裏也真不是個問題...（按Ctrl + F查找你的問題沒有 「？」 字符）通常我們（在Stack Overflow）要求您顯示您什麼嘗試，並問問你有什麼問題。請參閱：http://tinyurl.com/so-hints – Crisfole 2011-03-10 17:46:36
我不明白「讓他們在哪裏」的要求。在您的輸入中，1的數量超過了0的數量。那麼，你究竟是什麼離開了「他們在哪裏」？ – AnT 2011-03-10 23:32:26
你的例子有更多的1比0，但它不會離開他們所在的一切。 – 2011-03-10 23:42:26