Упорядочить 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

Вот решение, которое работает для массива 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's go to the left.
           pos++;
       }
   } 
}

Answer 2

Моя реализация в 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.

Answer 3

Вот мой (полный) удар в C #. Он генерирует список и вставляет случайных сотрудников, поэтому сделайте numberOfEmployees как хотите. Я понимаю, что, возможно, есть более простой способ сделать это, потому что в оригинальном плакате указывалось, что количество сотрудников с 0 отделами равно количеству сотрудников с 1 отделом, но я не мог с собой поделать.

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

    }
}

Answer 4

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

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)

Answer 5

Легко:

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

Answer 6

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

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

РЕДАКТИРОВАТЬ: новый пример помогает. Преимущество моего алгоритма, хотя он и медленнее, чем линейное время в худшем случае, состоит в том, что он использует только O (n) в использовании памяти. Поскольку единицы и нули являются только ключами для более крупных объектов (которые могут быть произвольно большими), может возникнуть проблема с памятью.