Упорядочить 0 и 1 в массиве
Это один из вопросов интервью, который у меня был недавно. Я хотел бы узнать другое восприятие подхода к этой проблеме.
Вопрос:
Вам предоставляется структура, в которой содержатся данные сотрудника с двумя элементами, int
department и string
name.
struct Employee
{
string Name;
int Dept;
}
Вам предоставлены сведения о N сотрудниках, среди которых сотрудники N/2 имеют Dept == 0
, а сотрудники N/2 имеют Dept == 1
, расположенных в произвольном порядке. Вам нужно отсортировать данные о сотрудниках на основе их значения Dept
, и это должно быть stable, то есть порядок 1s и 0s в оригинальная запись должна быть сохранена.
Например, учитывая следующие данные примера:
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), с постоянным пространством для дополнительных переменных (что означает, что сортировка должна выполняться на месте).
Ответы
Ответ 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;
}