Organiser 0 & amp; 1 dans un tableau

C'est une question d'entrevue que j'ai eue récemment. Je voudrais connaître les autres, de la perception de l'approche de ce problème.

Question:

Vous êtes donné une structure qui détient les informations sur les employés avec deux éléments, int département et string nom.

struct Employee
{ 
    string Name;
    int Dept;
}

Vous êtes donné les détails de N personnes, parmi lesquelles N/2 employés ont Dept == 0 et N/2 employés ont Dept == 1aménagées dans un certains ordre arbitraire. Vous avez besoin de trier les détails de l'employé en fonction de leur Dept valeur et il devrait être stable c'est à dire, de l'ordre de 1s et 0s dans le document original doit être maintenu.

Par exemple, étant donné les données d'exemple suivantes:

Nom Dept 

X1 0 
X2 1 
X3 0 
X4 1 
X5 0

après le tri, le résultat devrait être:

Nom Dept 

X2 1 
X4 1 
X1 0 
X3 0 
X5 0

L'algorithme doit être stable et la complexité du temps devrait être O(N), avec la constante de l'espace pour les autres variables (ce qui signifie que le tri doit être fait sur place).

source d'informationauteur

algorithm language-agnostic

20

Allouer un second tableau (O(N)). Itérer premier tableau et déplacer tous les 1 dans l'ordre où ils apparaissent pour la deuxième tableau. Itérer encore et déplacer le 0 qui sont à gauche, dans le même ordre pour la deuxième tableau. Toutes les opérations en O(N). Ce n'est PAS in situ (sur place) solution. Un non-stable in situ solution est obtenue par l'exécution du tri rapide de l'algorithme de partitionnement fois.

Après avoir effectué quelques recherches, il semble que la plus connue O(N) solutions sans aucune mémoire supplémentaire ne sont pas stables. Il est la recherche universitaire sur l'efficacité de 0-1 stable tri in situ (sur place), mais les solutions besoin de plus de mémoire. Je me demande si le premier énoncé du problème n'a pas été reproduit dans un exact de la mode. Sans exigence de stabilité, le problème est très facile; il est également facile sans in situ exigence. Avec à la FOIS des exigences (in situ, stable), la solution semble être insaisissable.

Parmi les réponses ici, il existe un algorithme qui fonctionne en temps O(N) et in situ, mais seulement si le champ clé est (1) mutables et (2) peut contenir un entier au lieu d'un seul bit. Cela fonctionne, mais n'est pas in situ 0-1 stable de tri, car il est supposé qu'il n'y est O(log N) en écriture de la mémoire disponible pour chaque élément du tableau.
13

Okey, voici ma démarche.

e.g a[] = { 1,0,0,0,1,1,1,0,0,1};

Pseudocode:
1. Avoir deux compteurs, count1 = 0 et count2 = (n/2)+1
2. De parcourir à travers le tableau,
```
if(arr[ i ] == 1) 
{ 
    arr[ i ] = count1++;
} else { 
    arr[ i ] = count2++ 
};
```
3. À la fin de la traversée, vous avez de tableau rempli de chiffres de 0 à n-1 comme:
```
a[ ] = { 0, 5, 6, 7, 1, 2, 3, 8, 9 4}
```
4. Maintenant, le problème vient de tri au-dessus de la résultante de tableau, ce qui peut être fait en O(N) comme ci-dessous:
```
for(j = 0; j <= 1; j++)  
{
    for(i = 0; i<n; i++)  
    {  
        if(arr[ i ] != i)  
        {  
            swap(arr[ i ], arr[ arr[ i ] ]);  
        }  
    }  
}
```
  Note: j boucle ne s'exécute que deux fois indépendamment sur " n " et a constante de la complexité. La commande de l'ensemble de cette boucle est de 2*n = O(n).
5. Après le tableau est trié, à Nouveau de parcourir à travers la matrice et de l'ensemble des éléments arr[0] à arr[n/2] à '1' et arr[(n/2)+1] à arr[n] comme '0'.
Espace complexité est constant et le temps de la complexité est O(etape 2) + O(etape 4) + O(etape 5) = n + 2n +n = 4*n = O(n).
6

à l'aide de std::stable_partition avec std::equal_to et std::binder1st devrait faire l'affaire dans une belle, fonctionnelle, STL comme:
```
using namespace std
stable_partition(&array[0], &array[N], binder1st(equal_to(), 1));
```
Bien sûr, cela suppose que les éléments du tableau ont certains de comparaison définie par l'opérateur (c'est à dire vous pouvez dire array[i]==1...). Si ils sont tout entiers, il n'aurait pas de sens de maintenir l'ordre ...

De la complexité: pour être O(N)stable_partition a besoin de plus de mémoire. Si l'algorithme ne parvient pas à allouer de la mémoire supplémentaire, il effectue dans O(N log N).

Utilisé ints au lieu de bits pour des raisons de simplicité, mais le concept sous-jacent est le même. Non pas que l'ordre les différentes 1s et 0s à la fin dans les questions!

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

Mis à jour pour les employés problème. Ajout d'un employé supplémentaire que la question initiale a dit qu'il y avait N/2 de chaque sorte, il y a un nombre pair, pour que ce soit vrai. Sinon, c'est la même chose.

Pas sûr que cette compile maintenant il faut le traiter comme le pseudo-code!

2

Le problème d'origine du texte de ne pas mentionner tous les autres champs à l'exception de l'entier (il a été modifié depuis).

Dans ce cas, la stabilité n'a pas de sens étant donné deux nombres égaux sont par ailleurs identiques. La solution est de simplement parcourir le tableau et mettre 1 n/2 fois et ensuite 0 n/2 fois.
1

Ce sera la première étape de tri radix.
0

En termes abstraits, vous pouvez utiliser une version modifiée de tri d'insertion, en remplaçant les valeurs zéro à droite, ainsi que toutes les valeurs de la gauche. Qui aurait une plus grande complexité de O(n), cependant.

Je suis un peu confus pourquoi la commande des questions, comme indiqué précédemment, les octets sont indiscernables.

EDIT: Le nouvel exemple aide. L'avantage de mon algorithme, même si c'est plus lent que le temps linéaire dans le pire des cas, c'est que c'est seulement O(n) dans l'utilisation de la mémoire. Puisque les uns et de zéros ne sont que des touches pour les gros objets (qui peuvent être arbitrairement grand), la mémoire peut être un sujet de préoccupation.

Ce que le diable, ici, c'est l'ensemble de la solution:
arr est la liste des éléments, point.l'id est 0 ou 1, stockées sous forme de int.

Ce code se déplace le 0s à l'avant.

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)

Mon implémentation en Perl à l'aide de simples pondération.

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;

Nom Dept 

X2 1 
X4 1 
X1 0 
X3 0 
X5 0

La sortie de <=> et cmp comparaisons est une valeur de -1,0,1.

En multipliant l'un des camparisons par deux nous obtenons un de -2,0,2.

Après l'ajout de la valeur de l'autre opérateur, nous obtenons un de -3,-2,-1,0,1,2,3

Je voulais voir comment de nombreuses comparaisons, il le ferait, j'ai ajouté quelques informations de débogage et est venu avec cette.

 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.

Voici une solution qui fonctionne pour un tableau de int. Vous pouvez le modifier.

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

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

0

Il peut être fait en une seule passe et en place.
1. Prendre deux variables pour l'indexation. On va point à la 0e position d'autres souligneront
  
  dernière position de l'élément.
2. Boucle jusqu'à ce que l'indexation des variables de l'égalité ou de la croix les uns des autres.
3. À partir de la première position de recherche de valeur 1 et à partir de la dernière position de recherche de valeur 0
  
  le swap à la fois les éléments. En un seul passage, nous pouvons trier le tableau en O(n) fois.
Ex:
#include
#define N 6
int main()
{
int list[N]={1,1,0,0,0,0};
int s,fin,tmp;
s=0;fin=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;
}
```

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

}

-1

Facile:

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

Et si vous voulez vraiment avoir la même 1s et 0s:

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

-1

Voici mon (complet) coup de couteau à en C#. Il génère la liste et les bâtons aléatoire employés, afin de faire numberOfEmployees ce que vous voulez. Je me rends compte il y a probablement un moyen plus simple de le faire, parce que l'affiche originale spécifié qu'il y a une quantité égale de 0-dept employés 1-service des employés, mais je ne pouvais pas m'en empêcher.

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

    }
}

-1

Je ne peux penser à un algorithme qui permettra de prendre en O(n + i) temps (dans le pire des cas O(2n-1) et dans le meilleur des cas O(n)) et pas d'espace supplémentaire. Nous commençons la traversée de la matrice de 0 à n-1 et à chaque fois que nous rencontrons un 1 on incrémente un compteur et les remplacer 1 par 0. Maintenant, quand nous avons atteint la fin du tableau, nous allons commencer à se déplacer vers l'arrière comme beaucoup de comptoir et d'initialiser chaque nombre avec 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;
}
```

Vous devez vous connecter pour publier un commentaire.