Étant donné un tableau d'entiers positifs et négatifs, réorganisez-le de sorte que vous ayez des entiers positifs à une extrémité et des entiers négatifs à l'autre

Question

Je suis récemment tombé sur un Microsoft Question d'Entrevue pour l'Ingénieur Logiciel.

Étant donné un tableau d'entiers positifs et négatifs, ré-organiser de façon à ce que vous avez des entiers positifs sur l'une des extrémités et des entiers négatifs sur les autres, mais conservent leur ordre d'apparition dans le tableau d'origine.

Par exemple, [1, 7, -5, 9, -12, 15]
La réponse serait: [-5, -12, 1, 7, 9, 15]

Cela devrait être fait en O(n).

On pourrait facilement le faire en O(n), mais je ne suis pas en mesure de penser à la façon dont nous pouvons maintenir l'ordre des éléments dans le tableau d'origine. Si nous oublions O(n) la complexité, quelqu'un pourrait-il me dire comment on peut conserver l'ordre des éléments, sans prendre en considération le temps et l'espace de la complexité.

EDIT: Dans la question qui nous sont nécessaires pour avoir O(1) espace de complexité aussi.

Answer 1

Pour parvenir à ce résultat dans la constante de l'espace (mais quadratique du temps), vous pouvez utiliser les deux la le d'attente d'approche en plaçant une file d'attente à chaque extrémité du tableau (similaire à la hollandaise Drapeau National de l'algorithme). Éléments de lecture de gauche à droite : l'ajout d'un élément à gauche de la file d'attente moyen le laisser seul, l'ajout d'un élément à droite de la file d'attente signifie transférer tous les éléments non dans une file d'attente vers la gauche par un, et de placer l'élément ajouté à la fin. Ensuite, pour concaténer les files d'attente, il vous suffit d'inverser l'ordre des éléments dans la seconde file d'attente.

Ce rapport effectue un O(n) opération (déplacement des éléments de la gauche) jusqu'à O(n) fois, ce qui donne un O(n2) temps de fonctionnement.

En utilisant une méthode similaire à la fusion de tri, vous pouvez réduire le temps O(n log n) complexité: découper le tableau en deux moitiés, de manière récursive les trier en fonction de la forme [N P] [N P] swap le premier P avec le deuxième N en O(n) fois (ça devient un peu délicat quand ils n'ont pas exactement la même taille, mais il est toujours linéaire).

Je n'ai absolument aucune idée de comment obtenez ce vers le bas à O(n) fois.

EDIT: en fait, votre liste liée insight est à droite. Si les données sont fournies comme une liste doublement chaînée, vous pouvez mettre en œuvre les deux-file d'attente de stratégie en temps O(n) le temps, O(1) de l'espace:

sort(list):
  negative = empty
  positive = empty
  while (list != empty)
     first = pop(list)
     if (first > 0) 
         append(positive,first)
     else
         append(negative,first)
  return concatenate(negative,positive)

Avec une liste chaînée de mise en œuvre qui garde des pointeurs pour les premier et dernier éléments, puis de la pop, de l'ajout et de concaténer sont tous O(1) opérations, de sorte que le total de la complexité est O(n). Comme pour l'espace, aucun des opérations d'allouer de la mémoire (append utilise simplement la mémoire publié par pop), il est donc O(1) dans l'ensemble.

Answer 2

Voici une version constante de la solution spatiale O (n) temps O (1), elle suppose que maxValue * (maxValue + 1) est inférieur à Integer.MAX_VALUE, où maxValue est le résultat de la valeur maxmum moins la valeur minmum dans le tableau. Il utilise le tableau d'origine comme tableau temporaire pour stocker le résultat.

 public static void specialSort(int[] A){
    int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
    for(int i=0; i<A.length; i++){
        if(A[i] > max)
            max = A[i];
        if(A[i] < min)
            min = A[i];
    }
    //Change all values to Positive
    for(int i=0; i<A.length; i++)
        A[i]-= min;

    int newMax = max-min+1;

    //Save original negative values into new positions
    int currNegativeIndex = 0;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax < (-min))
            A[currNegativeIndex++] += (A[i]%newMax)*newMax;
    //Save original positive values into new positions
    int currPositiveIndex = currNegativeIndex;
    for(int i=0; i<A.length; i++)
        if(A[i]%newMax > (-min))
            A[currPositiveIndex++] += (A[i]%newMax)*newMax;
    //Recover to original value 
    for(int i=0; i<A.length; i++){
        A[i] = A[i]/newMax + min; 
    }
}
 

Answer 3

Je ne suis pas sûr de comprendre correctement à la question, la réponse semble être trop simple:

• Promenade à travers le tableau et compter les nombres négatifs - O(n)
• Créer un nouveau tableau de taille O(n)
• Promenade par le biais du tableau d'origine et placer des nombres dans le nouveau tableau. Utiliser le nombre connu des nombres négatifs pour compenser les effets positifs - O(n)

Voici un moyen rapide de le faire en Python. Il est quelque peu différente de la première création d'un tableau pour les négatifs, en ajoutant les points positifs. Il n'est donc pas aussi efficace, mais toujours O(n).

>>> a = [1,7,-5,9,-12,15]
>>> print [x for x in a if x < 0] + [y for y in a if y >= 0]
[-5, -12, 1, 7, 9, 15]

Edit: Ok, maintenant, avec O(1) espace de complexité, il devient beaucoup plus difficile. Je suis intéressé par la façon de l'atteindre en O(n) le temps de la complexité, trop. Si cela peut aider, voici un moyen de garder le joint(1) l'espace de la complexité, mais nécessite O(n^2) complexité:

• Commencer à partir de la gauche de nombre négatif. Promenade à travers la matrice jusqu'à ce que vous trouver la prochaine nombre négatif.
• Dans une nouvelle boucle, change le numéro du négatif avec le nombre positif gauche. Faites cela jusqu'à ce que vous atteignez l'autre des nombres négatifs. Cela garantit l'ordre des numéros reste inchangé.
• Rincer et répéter jusqu'à ce que vous atteignez la fin de la matrice lors de la recherche d'un nouveau nombre négatif.

Answer 4

Vous pouvez utiliser 2 files d'attente et les fusionner. De cette façon, vous n'itérez qu'une seule fois sur le premier tableau et une fois sur chaque sous-file d'attente.

 negatives = []
positives = []

for elem in array:
  if elem >= 0:
    positives.push(elem)
  else
    negatives.push(elem)

result = array(negatives, positives)
 

Answer 5

Voici une solution avec seulement 2 itérations:
Disons que la longueur est n.
Et je vais utiliser du code comme C, ignorer les erreurs de syntaxe.

 solution[n];
for (i= 0,j=0 ; i < n ; i++ ) {
     if (array[i] < 0) solution[j++] = array[i];
}
for (i = n-1,j=n-1 ; ; i > 0 ; i--) {
     if (array[i] >= 0) solution[j--] = array[i];
}
 

L'idée est de le parcourir une fois et d'écrire tous les négatifs que nous rencontrons.
Passez ensuite en revue la deuxième fois depuis la fin et notez les points positifs de la fin vers le début.