Упорядочить 0 и 1 в массиве

Ответ 1

Okey, вот мой подход.

например, [] = {1,0,0,0,1,1,1,0,0,1};

псевдокод:

• У вас есть два счетчика: count1 = 0 и count2 = (n/2)+1

• Пройдите через массив,

  if(arr[ i ] == 1) 
  { 
      arr[ i ] = count1++;
  } else { 
      arr[ i ] = count2++ 
  };
  

• В конце обхода у вас есть массив, заполненный цифрами от 0 до n-1, например:

  a[ ] = { 0, 5, 6, 7, 1, 2, 3, 8, 9 4}
  

• Теперь возникает проблема сортировки полученного результирующего массива, это можно сделать в O (N), как показано ниже:

  for(j = 0; j <= 1; j++)  
  {
      for(i = 0; i<n; i++)  
      {  
          if(arr[ i ] != i)  
          {  
              swap(arr[ i ], arr[ arr[ i ] ]);  
          }  
      }  
  }
  

  Примечание: j цикл работает только дважды независимо от 'n' и имеет постоянную сложность. Порядок этого целого цикла равен 2 * n = O (n).

• После сортировки массива снова пройдите через массив и установите элементы arr[0] на arr[n/2] на '1' и arr[(n/2)+1] на arr[n] как '0'.

Сложность пространства постоянна, а временная сложность - O (шаг2) + O (шаг4) + O (шаг 5) = n + 2n + n = 4 * n = O (n).

Ответ 2

Выделите второй массив (O (N)). Итерации через первый массив и перемещение всего 1 в порядке их появления во второй массив. Итерации снова и переместите 0, оставшиеся в том же порядке, во второй массив. Все операции O (N). Это НЕ на месте (на месте). Нестабильное решение in situ получается путем запуска алгоритма разбиения Quicksort один раз.

После проведения некоторых исследований кажется, что известные O (N) решения без какой-либо дополнительной памяти нестабильны. Имеются академические исследования по эффективной стабильной сортировке 0-1 на месте (на месте), но решения требуют некоторой дополнительной памяти. Интересно, не было ли воспроизведено оригинальное постановка задачи точно. Без требования к стабильности проблема очень проста; это также легко без требований in situ. С BOTH требований (in situ, stable) решение кажется неуловимым.

Среди ответов здесь есть алгоритм, который работает в O (N) и находится in situ, но только если ключевое поле является (1) изменчивым и (2) может содержать целое число вместо одного бита. Это работает, но не является устойчивой сортировкой in situ 0-1, поскольку предполагается, что для элемента массива имеется доступная запись (log N).

Ответ 3

используя std::stable_partition вместе с std::equal_to и std::binder1st, должен сделать трюк в хорошем, функциональном STL-подобном способе:

using namespace std
stable_partition(&array[0], &array[N], binder1st(equal_to(), 1));

Конечно, это предполагает, что элементы массива имеют определенный оператор сравнения (т.е. вы можете сказать array[i]==1...). Если они являются целыми числами, не имеет смысла поддерживать порядок...

Что касается сложности: для того чтобы быть O (N), stable_partition требуется дополнительная память. Если алгоритм не может выделить эту дополнительную память, он выполняет в O (N log N).

Ответ 4

В исходном тексте проблемы не упоминалось никаких других полей, кроме целого (с тех пор редактировалось).

В таком случае устойчивость не имеет смысла, поскольку в противном случае два равных числа неразличимы. Решение состоит в том, чтобы просто пересечь массив и поставить 1 n/2 раза, а затем 0 n/2 раза.

Ответ 5

Вместо простоты используются биты для простоты, но базовая концепция одинаков. Не то, чтобы порядок отличался от 1 и 0 в вопросах!

var emps = new[] 
           {
               new Employee(X1, 0),
               new Employee(X2, 1),
               new Employee(X3, 0),
               new Employee(X4, 1),
               new Employee(X5, 0),
               new Employee(X6, 1)
           };

var sortedEmps = new Employee[bits.Length];

var oneIndex = 0;
var zeroIndex = bits.Length/2;

foreach (var employee in employees)
{
    if (employee.Dept  == 1)
        sortedEmps[oneIndex++] = employee;
    else
        sortedEmps[zeroIndex++] = employee;
}

Обновлено для проблемы с сотрудниками. Добавлен дополнительный сотрудник, поскольку в исходном вопросе говорилось, что их было N/2, поэтому для этого должно быть четное число. В противном случае это то же самое.

Не уверен, что теперь это компилируется, поэтому рассматривайте его как псевдокод!

Ответ 6

Это будет первый шаг сортировка radix.

Ответ 7

В абстрактных терминах вы можете использовать модифицированную сортировку вставки, заменяя все нулевые значения вправо и все значения слева. Тем не менее, это будет сложнее, чем O (n).

Я немного смущен, почему вопросы упорядочения, как было указано ранее, байты неразличимы.

EDIT: Новый пример помогает. Преимущество моего алгоритма, хотя оно медленнее линейного времени в худшем случае, заключается в том, что он использует только O (n) в использовании памяти. Поскольку те и нули являются только ключами для больших объектов (которые могут быть сколь угодно большими), память может быть проблемой.

Ответ 8

Что, черт возьми, вот целое решение: arr - список элементов, item.id - 0 или 1, сохраненный как int.
Этот код перемещает 0s вперед.

count = { 0:0, 1:len(arr)/2 }
for ii in range(len( arr )):
  id = arr[ii].id
  arr[ii].id = count[id]
  count[id] += 1
for ii in range(len( arr )):
  while arr[ii].id != ii:
    T = arr[ii]
    arr[ii] = arr[arr[ii].id]
    arr[T.id] = T
for ii in range(len( arr )):
  arr[ii].id = (ii >= len(arr)/2)

Ответ 9

Моя реализация в Perl с использованием простого взвешивания.

use Modern::Perl;

my @data;
{
  use List::MoreUtils qw'natatime';
  my $iter = natatime 2, qw'
    X1  0
    X2  1
    X3  0
    X4  1
    X5  0
  ';

  while( my($a,$b) = $iter->() ){
    push @data, [$a,$b]
  }
}

my @sorted = sort {
  ($a->[1] <=> $b->[1]) * -2 + # gives more weight to second element
  ($a->[0] cmp $b->[0])
} @data;

say "Name\tDept\n";
say join "\t", @$_ for @sorted;

Name    Dept

X2      1
X4      1
X1      0
X3      0
X5      0

Вывод сравнения <=> и cmp - это значение -1,0,1.
Умножая один из кампаферов на два, мы получаем один из -2,0,2.
После добавления значения другого оператора получим один из -3,-2,-1,0,1,2,3

Я хотел посмотреть, сколько сравнений он сделает, поэтому я добавил некоторую отладочную информацию и придумал это.

 a           b        a1      b1     a0     b0
X1,0   ->   X2,1      0   --> 1      X1 <-  X2
X3,0   ->   X4,1      0   --> 1      X3 <-  X4
X2,1  <-    X4,1      1   -   1      X2 <-  X4
X4,1  <-    X1,0      1 <--   0      X4  -> X1
X1,0  <-    X3,0      0   -   0      X1 <-  X3
X2,1 <<-    X5,0      1 <--   0      X2 <-  X5
X5,0   ->>  X4,1      0   --> 1      X5  -> X4
X5,0   ->   X1,0      0   -   0      X5  -> X1
X5,0   ->   X3,0      0   -   0      X5  -> X3

The arrows point at the earlier value.

Ответ 10

Вот решение, которое работает для массива int. Вы можете изменить его.

sort (int [] a) {
   int pos = 0;
   for (int i = 1; i < a.length; i++) {
       if (a[i] == 0 && a[pos] == 1) {
           swap(a, pos, i);   // this makes all 0 go to the left.
           pos++;
       }
   } 
}

Ответ 11

#include<stdio.h>
//#include<conio.h>

int main()
{
  int i,a[20]={0};
  int *ptr1,*ptr2;
  //clrscr();
  //a[2]=a[4]=a[6]=a[8]=a[16]=1;
  a[19]=a[18]=1;

  for(i=0;i<20;i++)
    printf("%d",a[i]);

  printf("\n\nafter");

  ptr1=ptr2=a;
  for(i=0;i<20;i++)
  {
    if(*ptr1==0&&*ptr2==1)
    {
      int temp=*ptr1;*ptr1=*ptr2;*ptr2=temp;
      ptr1++;ptr2++;
    }
    else if(*ptr1==1&&*ptr2==0)
    {
      ptr1++;ptr2++;
    }
    else if(*ptr1==0&&*ptr2==0)
    {
      ptr2++;
    }
    else
    {
      if(ptr1<ptr2)
        ptr1++;
      else
      {
        ptr1++;ptr2++;
      }
    }
  }

  for(i=0;i<20;i++)
  {
    printf("%d",a[i]);
  }

 // getch();

  return 0;
}

Ответ 12

Это можно сделать за один проход и на месте.

• Возьмем две переменные для индексирования. Один будет указывать на 0-ю позицию, другая указывает на последней позиции элемента.
• Цикл до тех пор, пока переменные индексации не будут равны или не пересекаются друг с другом.
• С первой позиции найдите значение 1 и из последней позиции найдите значение 0
  затем поменяйте оба элемента. За один проход мы можем отсортировать массив в O (n) времени.

Пример:   #включают   #define N 6   int main()   {       int list [N] = {1,1,0,0,0,0};       int s, end, tmp;       s = 0; конец = N-1;

    while(s less than end)
    {
        if(list[s]==1)
        {
            while(list[end] == 1) 
               end--;

            if(list[end] == 0 && s less than end)
            {
                tmp = list[s];
                list[s] = list[end];
                list[end] = tmp;
                s++;end--;
            }
        }
        else s++;
    }
    for(s=0;s less than N;s++)
    {
        printf("%d ",list[s]);
    }
    return;
}

Ответ 13

left = 0;
right = n-1;

while(left<right){

while(left < right && array[left]==0){
    left++;
}

while(left < right && array[right]==1){
    right--;
}

while(left<right){
    array[left]=0;
    array[right]=1;
    left++;
    right--;    
}

}

Ответ 14

Легко:

function sort(array):
    new_array = new Array(array.length)
    x = 0
    for(i : array): if(i): new_array(x++) = 1
    return new_array

И если вы действительно хотите иметь одинаковые 1 и 0:

function sort(array):
    new_array = new Array(array.length)
    x, y = 0, array.length / 2
    for(i : array):
        if(i): new_array(x++) = i
        else:  new_array(y++) = i
    return new_array

Ответ 15

Здесь мой (полный) удар в него на С#. Он генерирует список и кладет случайных сотрудников, поэтому < <20 > сделайте все, что захотите. Я понимаю, что есть, вероятно, более простой способ сделать это, потому что в оригинальном плакате указано, что в качестве сотрудников с 1 делом имеется равное количество сотрудников 0-депт, но я не мог с собой поделать.

struct Employee
{
    public Employee(string name, int dept)
    {
        this.name = name;
        this.dept = dept;
    }

    public string name;
    public int dept;
}

class Program
{
    static void Main(string[] args)
    {
        int numberOfEmployees = 100;
        Random r = new Random();

        Employee[] emps = new Employee[numberOfEmployees];
        var empBuf = new Employee[numberOfEmployees];
        int nextAvail = 0;

        // Initialize array of employees with random data
        for (int i = 0; i < numberOfEmployees; i++)
        {
            emps[i] = new Employee("x" + i.ToString(), r.Next(0, 2));
        }

        Console.WriteLine("Old list:");
        foreach (var e in emps)
        {
            Console.WriteLine("Name: {0}, Dept: {1}", e.name, e.dept);
        }

        // throw employees with dept == 1 in first
        for (int i = 0; i < numberOfEmployees; i++)
        {
            if (emps[i].dept == 1)
            {
                empBuf[nextAvail] = emps[i];
                nextAvail++;
            }
        }

        // stick the employees with dept == 0 in last
        for (int i = 0; i < numberOfEmployees; i++)
        {
            if (emps[i].dept == 0)
            {
                empBuf[nextAvail] = emps[i];
                nextAvail++;
            }
        }


        Console.WriteLine("New list:");
        foreach (Employee e in empBuf)
        {
            Console.WriteLine("Name: {0}, Dept: {1}", e.name, e.dept);
        }

    }
}

Ответ 16

Я могу вспомнить алгоритм, который займет время O (n + i) (наихудший случай O (2n-1) и лучший случай O (n)) и лишнее пространство. Мы начинаем перемещаться по массиву от 0 до n-1, и каждый раз, когда мы сталкиваемся с 1, мы увеличиваем счетчик и заменяем его 1 на 0. Теперь, когда мы достигли конца массива, мы начнем двигаться назад, так как счетчик и инициализация каждое число с 1.

private static int[] foo(int[] array) {

int counter = 0;
int i;

for(i = 0; i < array.length; i++) {
if (array[i] == 1) {
    array[i] = 0;
    counter++;      
}
}

while(counter > 0) {
array[--i] = 1;
counter--;
}
return array;
}