Écrivez une fonction qui fait tourner un tableau entier d'un nombre donné k. k éléments de la fin doivent se déplacer au début du tableau, et tous les autres éléments doivent se déplacer vers la droite pour créer l'espace.
La rotation doit être effectuée sur place.
L'algorithme ne doit pas fonctionner dans plus de O (n), où n est la taille du tableau.
Une mémoire constante doit également être utilisée pour effectuer l'opération.
Par exemple,
si le tableau est initialisé avec les éléments arr = {1, 2, 3, 4, 5, 6, 7, 8, 9}
rotation (arr, 3) fera que les éléments seront {7, 8, 9, 1, 2, 3, 4, 5, 6}
rotation (arr, 6) entraînera le {4, 5, 6, 7, 8, 9, 1, 2, 3}
popularity-contest
array-manipulation
microbien
la source
la source
Réponses:
C (104)
Minifié:
la source
a <-- b
APL (4)
Je ne sais pas si APL en a réellement besoin, mais dans l'implémentation que j'ai vue (les internes de), cela prendrait du temps proportionnel à
A
, et une mémoire constante.la source
{⍵⌽⍨-⍺}
ou{⌽⍺⌽⌽⍵}
. Dans NARS2000, il peut être élégamment écrit comme⌽⍢⌽
.Voici une version C de longue haleine de l'idée de Colin.
la source
O(log(n))
opérations. Regardez àby
1, votre boucle `` j '' est s_arr / g ou N - ce sont des opérations O (N)C
Je ne sais pas quels sont les critères, mais comme je me suis amusé avec l'algorithme, voici mon entrée:
Je vais aussi jouer au golf pour une bonne mesure; 126 octets, peuvent être raccourcis:
la source
Je ne vois pas beaucoup de solutions C ++ ici, alors j'ai pensé que j'essaierais celle-ci car elle ne compte pas les caractères.
Ceci est une vraie rotation "sur place", utilise donc 0 espace supplémentaire (sauf techniquement swap et 3 pouces) et puisque la boucle est exactement N, remplit également la complexité O (N).
la source
std::rotate
parce que ce genre de but va à l'encontre du butSi vous effectuez tour à tour chacun des cycles de rotation possibles par n (il y en a GCD (n, len (arr))), vous n'avez besoin que d'une seule copie temporaire d'un élément de tableau et de quelques variables d'état. Comme ça, en Python:
la source
cycle
variable est de taille non constante. Vous devrez générer ce tableau au fur et à mesure.C (137 caractères)
Fonction
rotate
réduite à 137 caractères:la source
Factor a un type intégré pour les tableaux rotatifs
<circular>
, il s'agit donc en fait d'une opération O (1):Un équivalent Facteur moins tricheur de l'impressionnante solution C de Ben Voigt:
la source
JavaScript 45
Je suis allé au golf de toute façon parce que j'aime le golf. Il est au maximum O (N) tant que
t
<= taille du tableau.Pour gérer
t
n'importe quelle proportion en O (N), les éléments suivants peuvent être utilisés (pesant 58 caractères):Ne revient pas, modifie le tableau en place.
la source
r(o,t) => rot
REBEL - 22
Entrée: k exprimé sous la forme d'un entier unaire utilisant
_
comme chiffre, suivi d'un espace, puis d'un tableau d'entiers délimité par des espaces.Sortie: un espace, puis le tableau pivote.
Exemple:
État final:
Explication:
À chaque itération, il remplace un
_
et un tableau[array] + tail
partail + [array]
.Exemple:
la source
O(n)
, et vous faites cela plusieursn
fois.Java
Démo ici .
Javascript minimisé , 114 :
la source
Haskell
Il s'agit en fait de θ (n), car la division est θ (k) et la jointure est θ (nk). Pas sûr de la mémoire cependant.
la source
Python 3
Complexité temporelle O (n) de la mémoire constante
la source
Python
la source
python
la source
vb.net O (n) (pas de mémoire constante)
la source
Rubis
la source
C (118)
Était probablement un peu trop indulgent avec certaines des spécifications. Utilise la mémoire proportionnelle à
shift % length
. Peut également tourner dans le sens opposé si une valeur de décalage négative est transmise.la source
Python 2, 57
Si seulement
l[-n:len(l)-n]
ça fonctionnait comme je m'y attendais. Il revient juste[]
pour une raison quelconque.la source
Quelqu'un pourrait-il s'il vous plaît vérifier si cela répond réellement aux exigences? Je pense que oui, mais je n'ai pas encore étudié le CS.
la source
C ++, 136
la source
Java
Échangez les k derniers éléments avec les premiers k éléments, puis faites pivoter les éléments restants de k. Lorsqu'il vous reste moins de k éléments à la fin, faites-les pivoter de k% du nombre d'éléments restants. Je ne pense pas que quiconque ci-dessus ait adopté cette approche. Effectue exactement une opération de swap pour chaque élément, fait tout en place.
la source
Perl 5 , 42 octets
Essayez-le en ligne!
Le sous-programme prend la distance de rotation comme premier paramètre et une référence au tableau comme deuxième. Le temps d'exécution est constant en fonction de la distance de rotation. La taille du tableau n'affecte pas le temps d'exécution. Le tableau est modifié en place en supprimant un élément de droite et en le plaçant à gauche.
la source