Inverser un sous-tableau d'un tableau, en moins de O (n) temps

Question

comment pouvons-nous inverser un sous-tableau (disons du i-ième index au j-ième indice) d'un tableau (ou toute autre structure de données, comme linked-list (pas doublement)), en moins de O (n) temps? la consommation de temps O (n) est triviale (je veux faire cette réversion plusieurs fois sur le tableau, par exemple en commençant depuis le début et en l'inversant n fois (à chaque fois, avancer d'un index puis l'inverser à nouveau), donc il devrait y avoir un moyen, dont son analyse amortie nous donnerait une consommation de temps inférieure à O (n), une idée?
merci D'avance :)

Answer 1

Je pense que vous voulez résoudre ce problème avec une mauvaise approche. Je suppose que vous voulez améliorer l'algorithme dans son ensemble, et non l'inverse O (n). Parce que ce n'est pas possible. Vous avez toujours O (n) si vous devez considérer chacun des n éléments.

Comme je l'ai dit, ce que vous pouvez faire est d'améliorer l'algorithme O (n^2). Vous pouvez résoudre que O (n): Disons que nous avons cette liste:

a b c d e 

Vous modifiez ensuite cette liste en utilisant votre algorithme:

e d c b a 
e a b c d 

et ainsi de suite .. à la fin vous ont ceci:

e a d b c 

vous pouvez obtenir cette liste si vous avez deux pointeurs provenant des deux extrémités du tableau et alterner entre les pointeurs (incrément/décrément/obtenir la valeur). Ce qui vous donne O (n) pour toute la procédure.

explication plus détaillée de cet algorithme:

Utilisation de la liste précédente, nous voulons que les éléments dans l'ordre de suivi:

a b c d e 
2 4 5 3 1 

Vous créez deux pointeurs. Un pointage au début de la liste, l'autre à la fin:

a b c d e 
^  ^
p1  p2 

Ensuite, les algorithmes fonctionne comme suit:

1. Take the value of p2 
2. Take the value of p1 
3. Move the pointer p2 one index back 
4. Move the pointer p1 one index further 
5. If they point to the same location, take the value of p1 and stop. 
    or if p1 has passed p2 then stop. 
    or else go to 1. 

Answer 2

Comme mentionné duedl0r, O (n) est votre minimum. vous devrez déplacer n éléments à leur nouvelle position.

Depuis que vous avez mentionné une liste liée, voici une solution O (n) pour cela.

Si vous vous déplacez dans tous les nœuds et inversez leur direction, puis liez les extrémités au reste de la liste, la sous-liste est inversée. Alors:

1->2->3->4->5->6->7->8->9 

marche arrière 4 à 7 changerait:

4->5->6->7 

dans:

4<-5<-6<-7 

Ensuite, il suffit encore 3 points à 7 et laisser 4 points à 8.

copie Un peu le format de duedl0r cohérence:

1. Move to the item before the first item to reorder(n steps) 
2. remember it as a (1 step) 
3. Move to the next item (1 step) 
4. Remember it as b (1 step) 

while not at the last item to reorder: (m times) 
5. Remember current item as c (1 step) 
6. Go to next item (1 step) 
7. Let the next item point to the previous item (1 step) 

having reached the last item to reorder: 
8. let item a point to item c (1 step) 

if there is a next item: 
9. move to next item (1 step) 
10. let item b point to current item (1 step) 

C'est O (n + 1 + 1 + 1 + m * (1 + 1 + 1) + 1 + 1 + 1). Sans tous les nombres qui ne sont pas autorisés dans Big O, c'est O (n + m), qui peut être appelé O (n + n), qui peut être appelé O (2n).

Et c'est O (n).

Answer 3

Vous pouvez le faire O (n) heure pour tableau donné. Ici, l représente l'indice de départ et r représente la fin. Nous devons donc inverser le sous-réseau de r à l.

public void reverse(int[] arr, int l, int r) 
    { 
     int d = (r-l+1)/2; 
     for(int i=0;i<d;i++) 
     { 
     int t = arr[l+i]; 
     arr[l+i] = arr[r-i]; 
     arr[r-i] = t; 
     } 
    // print array here 
    }