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

Question

Это один из вопросов интервью, который у меня был недавно. Хотелось бы узнать у других восприятие подхода к этой проблеме.

Вопрос:

Вам дана структура, которая содержит данные о сотруднике с двумя элементами: int отдел и string имя.

struct Employee
{ 
    string Name;
    int Dept;
}

Вам дается информация о N Сотрудниках, среди которых N / 2 сотрудника имеют Dept == 0, а N / 2 сотрудника имеют Dept == 1, расположенные в произвольном порядке. Вам необходимо отсортировать данные о сотрудниках по их значению Dept, и оно должно быть стабильным , то есть порядок 1 и 0 в исходной записи должен сохраняться.

Например, с учетом следующих образцов данных:

Name         Dept

X1           0
X2           1
X3           0
X4           1
X5           0

после сортировки результат должен быть:

Name         Dept

X2           1
X4           1
X1           0
X3           0
X5           0

Алгоритм должен быть стабильным, а временная сложность должна быть O (N) с постоянным пространством для дополнительных переменных (что означает, что сортировка должна выполняться на месте).

Answer 1

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

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

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

Answer 2

Хорошо, вот мой подход.

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

псевдокод:

1. Есть два счетчика, count1 = 0 и count2 = (n/2)+1

2. Обход массива,

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

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

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

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).

5. После сортировки массива Снова просмотрите массив и установите элементы от 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).

Answer 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) .

Answer 4

Для простоты используются целые числа вместо битов, но основная концепция та же самая. Не то чтобы порядок, в котором разные 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 каждого из них должны быть четными, чтобы это было правдой. В противном случае это то же самое.

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

Answer 5

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

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

Answer 6

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

Answer 7

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

}

Answer 8

Я могу придумать алгоритм, который будет принимать 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;
}

Answer 9

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

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

Ex: #включают #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;
}

Answer 10

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