双色抖动

我有一个包含0s和1s混合的数组。我想重新排列数组的内容，以便数组中的偶数位数包含0和奇数位置尽可能包含1，但受限于0s和1s的数量不变。这意味着如果0s的数量超过1s的数量，反之亦然，那么在重新排列的数组的末尾会有一个块，包括all-0s或all-1s。如何在一次通过中修改阵列？例如：

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}

已邀请:

9 个回复

拟僚疽刊剔

你可以使用标准的双色排序算法;只需编辑数组引用，将对数组前半部分的访问映射到实际数组中的偶数元素，然后访问数组的后半部分到实际数组中的奇数元素（向后）。基本上，a[i]成为（假设size是偶数）：

a[i < size/2 ? i * 2 : (size - i) * 2 - 1]

梆晨灸碾

我不认为它可以在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;
    }
  }
}

凄嘛姥

循环遍历数组，维护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

姬第柔炒

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++;
    }
  }
}

久纳禾澎

这样做。结果与提出的输出不同，但是等于给出的规则（问题的文本不包括“排序”一词，只是在最后你必须移动所有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}

镰茧钩

这可以单程完成。这是另一种使用单次传递的解决方案。这个想法是保留两个索引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;
            }
        }
    }
}

田眯衅

#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;
        }
    }
}

骨酚柯

因为它只有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]);
}

要回复问题请先登录或注册

双色抖动

9 个回复

发起人

dithering

问题状态

双色抖动

与内容相关的链接

9 个回复

发起人

dithering

问题状态