Trouver le nombre de "swaps" nécessaires pour trier un tableau donné
C'est une question d'entrevue. Un swap
implique la suppression de tout élément de la matrice et d'ajouter à l'arrière de la même matrice. Étant donné un tableau d'entiers de trouver le nombre minimum de swaps
nécessaires pour trier le tableau. Pouvez-vous faire mieux que O(n^2)
?
Par exemple: tableau d'Entrée: [3124]. Le nombre de swaps
: 2 ([3124] -> [1243] -> [1234]).
source d'informationauteur Michael
Vous devez vous connecter pour publier un commentaire.
Cela peut fonctionner dans
O(nlogn)
même si nous ne présumons pas de tableau de valeurs consécutives.Si nous n' - il peut être fait dans
O(n)
.Une façon de le faire c'est avec
O(n)
de l'espace etO(nlogn)
temps.Tableau donné
A
trier (O(nlogn)
) dans un second tableauB
.maintenant... (les tableaux sont indexés à partir de 1)
Le problème se résume à trouver le plus long préfixe du tableau trié qui apparaît comme une sous-suite dans le tableau d'entrée. Ce qui détermine les éléments qui ne pas besoin d'être triés. Les éléments restants devront être supprimés un par un, de la plus petite à la plus grande, et ajouté à l'arrière.
Dans votre exemple,
[3, 1, 2, 4]
déjà triés sous-suite est[1, 2]
. La solution optimale est de supprimer la remaning deux éléments,3
et4
et de les ajouter à l'arrière. Ainsi, la solution optimale est de deux "swaps".Trouver le sous-suite qui peut être fait dans
O(n logn)
temps à l'aide deO(n)
de la mémoire supplémentaire. Le pseudo-code (le code se trouve également être valable Python):Si, comme dans votre exemple, le tableau contient une permutation des entiers de
1
àn
le problème peut être résolu enO(n)
temps à l'aide deO(1)
mémoire:Plus généralement, la deuxième méthode peut être utilisée chaque fois que nous connaissons le tableau de sortie a priori et donc n'ont pas besoin de le trouver par le biais de tri.
Observation: Si un élément est échangé à l'arrière, sa position précédente n'a pas d'importance. Aucun élément ne doit être échangé plus d'une fois.
Observation: Le dernier swap (le cas échéant) doit se déplacer le plus grand élément.
Observation: Avant le swap, le tableau (à l'exclusion du dernier élément) doivent être triés (par ex swaps, ou d'abord)
Algorithme de trien supposant que les valeurs sont conecutive: trouver le plus long triés sous-suite d'consécutives (en valeur) des éléments de départ à 1:
3 1 5 2 4
swap de tous les plus d'éléments à son tour:
1 5 2 4 3
1 5 2 3 4
1 2 3 4 5
De trouver le nombre de contrats de swaps de en O(n), trouver la longueur de la plus longue triés sous-suite d'une succession d'éléments en commençant à 1:
ensuite, le nombre de swaps = la longueur de l'entrée - la plus longue de ses triés sous-suite.
Une solution alternative ( O(n^2) ) si l'entrée n'est pas une permutation de 1..n:
Encore une autre solution ( O(n log n) ), en supposant des éléments uniques:
Si vous ne souhaitez pas copier l'entrée de tableau, trier par oldPos avant la dernière étape à la place.
@tous , la solution retenue fournis par @Itay karo et @NPE est totalement faux parce qu'il ne considère pas l'avenir de la commande des échangé des éléments...
Il échoue pour de nombreux cas de tests comme:
3 1 2 5 4
correcte de sortie: 4
mais de leur donner les codes de sortie comme 3...
explication: 3 1 2 5 4--->1 2 5 4 3--->1 2 4 3 5--->1 2 3 5 4--->1 2 3 4 5
PS:je cann, pas de commentaire il n'y en raison de la faible réputation
Cela peut être fait en O(n log n).
D'abord trouver le minimum de l'élément dans le tableau. Maintenant, trouver le max élément qui se produit avant cet élément. Appel ce
max_left
. Vous devez appelerswap()
pour tous les éléments avant de les min élément du tableau.Maintenant trouver de la plus longue sous-suite croissante du droit de la min élément, avec la contrainte que vous devriez sauter éléments dont les valeurs sont supérieures à max_left.
Le nombre requis de swaps est
size(array) - size(LIS)
.Par exemple, considérons le tableau,
7 8 9 1 2 5 11 18
Minimum élément dans le tableau 1. Nous avons donc trouver le max avant de l'élément minimum.
7 8 9 | 1 2 5 11 18
max_left = 9
Maintenant, trouver le LIS à droite de min avec des éléments < 9
LIS = 1,2,5
Pas de swaps = 8 - 3 = 5
Dans les cas où max élément est null, c'est à dire., min est le premier élément, trouver le LIS de la matrice et de la nécessaire réponse est la taille(array)-taille(LIS)
Par Exemple
2 5 4 3
max_left est null. SIL est
2 3
Pas de swaps = taille(array) - taille(LIS) = 4 - 2 = 2
Ce code renvoie le nombre minimal de swaps nécessaire pour trier un tableau en place.
Par exemple, Un[] = [7,3,4,1] En échangeant 1 et 7, nous obtenons [1,3,4,7].
de même, B[] = [1,2,6,4,8,7,9]. Nous avons d'abord swap de 6 à 4, donc, B[] -> [1,2,4,6,8,7,9]. Puis 7 à 8. Donc -> [1,2,4,6,7,8,9]
L'algorithme s'exécute en temps O(nombre de couples où la valeur d'index i < valeur à l'indice i-1) ~ O(N) .