circulaire de décalage vers la gauche d'un tableau de n positions en java

Je suis en train de faire la circulaire de décalage vers la gauche d'un tableau de n positions à l'aide d'un seul tableau 1D. Je peux le faire dans les deux tableaux, mais je n'ai pas compris comment le faire en utilisant un. Veuillez donner vos suggestions

InformationsquelleAutor user1588850 | 2012-08-09
  1. 20

    Il est en fait un algorithme intelligent pour cela. Nous allons utiliser A pour désigner la matrice, N pour désigner la taille de la matrice, et n pour indiquer le nombre de postes à changement. Après le changement que vous souhaitez le i-th élément à déplacer à la ((i + n) mode N)-th position, par conséquent, nous pouvons définir les postes par le mappage suivant:

    f(j) := (j + n) mod N  (j = 0,...,N - 1)

    L'idée générale derrière cet algorithme va comme ceci: Nous ne voulons pas de déplacer les éléments autour de plus nécessaire, de sorte que, idéalement, nous aimerions tout simplement de placer chaque élément dans c'est bon (déplacé) position sur le premier essai. Dites-nous commencer avec l'élément à la position i. Ce que nous voulons faire est de déplacer l'élément à la position i position f(i), mais ensuite, nous allons remplacer l'élément à cette position, nous devons d'abord enregistrer l'élément à la position f(i) et ensuite effectuer la maj. Une fois que nous avons changé le premier élément, nous avons besoin de choisir un autre élément à déplacer. Puisque nous voulons économiser de l'espace, le candidat est l'élément que nous venez d'enregistrer (l'élément qui était en position f(i)). Comme avant, nous économisons de l'élément à la position f(f(i)) puis copier nos enregistré élément dans cette position. Nous continuons à répéter ce processus (en passant par des postes de i, f(i), f(f(i)), f(f(f(i))), ...) jusqu'à ce que nous atteignons un élément que nous avons déjà décalé (qui nous sont gauranteed à faire, car il y a finitly beaucoup de position). Si nous avons passé en revue tous les éléments, alors nous sommes fait, si non, alors nous avons sélectionner un autre élément (qui n'a pas été déplacé encore), dire à la position j, et répétez la procédure (en passant par j, f(j), f(f(j)), f(f(f(j))), ...). C'est tout. Mais avant que nous puissions mettre en œuvre un tel algorithme, ou même avant de nous décider si c'est en effet un bon algorithme, nous avons besoin de répondre à quelques questions:

    1. Dire que nous parcourir les positions i, f(i), f(f(i)), .... Comment pouvons-nous dire que nous avons atteint une position qui a déjà été changé? Devons-nous sauver tous les postes que nous avons passé à travers? Si nous le faisons, alors cela signifie que nous devons tenir un tableau de taille N (pour couvrir toutes les positions), et nous avons aussi besoin pour effectuer une recherche à chaque fois que l'on passe d'un élément. ce serait faire l'algorithme terriblement innefficient. Heureusement, ce n'est pas nécessaire, puisque la séquence i, f(i), f(f(i)), ... devez enrouler autour de lui-même à la position i, donc nous avons seulement besoin d'attendre jusqu'à ce que nous arrivons à la position. Nous pouvons le prouver, ce qui assetion comme suit: Supposons que le premier élément répété que nous rencontrons n'est pas i. Nous devons alors avoir 2 différents éléments, que lorsqu'il est décalé arriverez à la même position - une contradiction.

    2. Dire que nous avons fini en passant par i, f(i), f(f(i)), ..., mais il y a encore des éléments qui restent unshifted (on peut dire par le calcul du nombre d'éléments nous avons changé). Comment faisons-nous maintenant à trouver une position j qui contient un tel élément? Et aussi, une fois que nous avons terminé cette deuxième itération (en passant par j, f(j), f(f(j)), ...) comment pouvons-nous trouver un troisième position k avec un unshifted élément? et ainsi de suite.. Cela aussi, nous devons enregistrer un tableau de compte pour utilisé\les éléments non utilisés, et perfrom une recherche à chaque fois que nous avons besoin de trouver un élément non utilisé. Toutefois, nous pouvons à nouveau se détendre, car, comme nous allons le découvrir bientôt, tous les positions de départ (que nous avons notée par i, j et k) sont adjacentes. ce qui signifie, que si l'on commence à partir de la position i, nous allons ensuite sélectionner i + 1, puis i + 2, et ainsi de suite...

    3. les séquences i, f(i), f(f(i)), ... et j, f(j), f(f(j)), ... (oùi et j sont différents) contiennent des éléments communs? Si ils font cela voudrait dire que l'algorithme est inutile, car il pourrait passer le meme element deux fois par l'amenant à se retrouver dans la mauvaise position. La réponse, puis (bien sûr), c'est qu'ils ne peuvent pas contenir d'éléments communs. Et nous allons voir pourquoi.

    Notonsd := gcd(N, n). Pour tous les entiers: i = 0,...,d - 1 nous définissons l'ensemble suivant:

    S(i) := { kd + i | k = 0,...,N/d - 1}

    Il est facile de voir que les jeux de S(0),...,S(d - 1), ensemble, couvrent l'ensemble {0,...,N - 1}. Nous observons également que lors de la division d'un élément dans un ensemble S(i) par d, nous sommes laissés avec le reste i, et en divisant un élément d'un autre ensemble S(j) par d va nous laisser avec un autre reste (j). Ainsi, deux ensembles contiennent un élément commun. Avec cela, nous avons établi que les jeux de S(0),...,S(d - 1) forment une partition de {0,...,N - 1}

    Maintenant, pour chaque i = 0,...,d - 1, nous allons définir l'ensemble T(i) comme i, f(i), f(f(i)), .... Par la définition de f nous pouvons écrire T(i) comme suit:

    T(i) = {(kn + i) mod N | k is an integer}

    Nous observons que si x est un élément de la T(i), alors on peut écrire pour certains k:

    x = (kn + i) mod N = (k(n/d)d + i) mod N

    Notons z := k(n/d) mod N/d, puis en multipliant par d, nous avons:

    kn mod N = zd

    et donc:

    x = (kn + i) mod N = zd + i

    Ainsi, x est aussi dans S(i). De même, Si l'on prend la y de S(i) nous observons que, pour certains k:

    y = kd + i

    Depuis gcd(n/d, N/d) = 1 il existe un q tels que q(n/d) mod N/d = 1 (modulaire inverse), donc on peut écrire (en multipliant par kd):

    kd = kqn mod N

    et donc:

    y = kd + i = ((kq)n + i) mod N

    Ainsi, y est aussi dans T(i). Nous concluons que T(i) = S(i). De ce fait, nous pouvons facilement montrer notre précédente assetions. Tout d'abord, depuis les ensembles forment une partition de {0,...,N - 1} la troisième assertion (pas de deux séquences contiennent un élément commun) est satisfaite. Deuxièmement, par la définition des ensembles de S(i) nous pouvons prendre n'importe quel groupe de d les éléments adjacents dans {0,...N - 1} et chacun d'eux sera placé dans un autre ensemble. Cela répond à la seconde affirmation.

    Ce que cela signifie est que l'on peut faire tourner tous les éléments dans des positions 0, d, 2d, ..., (N/d - 1)d par le simple remplacement de l'élément à la position n mod N avec l'élément à la position 0, l'élément à la position 2n mod N avec l'élément à la position n mod N, et ainsi de suite ... jusqu'à notre retour à l'élément en position 0 (qui nous sont assurés qui va arriver). Voici un pseudo-code exemple:

    temp <- A[0]
j <- N - (n mod N)
while j != 0 do
    A[(j + n) mod N] <- A[j];
    j <- (j - n) mod N
A[n mod N] <- temp;

    Ce couvre l'ensemble S(0). Pour couvrir le reste des séries, à Savoir S(1), ... ,S(d-1), il vous suffit de faire une itération sur chaque jeu de la même manière que nous avons fait pour la première:

    for i <- 0 to d - 1
    temp <- A[i]
    j <- N - ((n - i) mod N)
    while j != i do
        A[(j + n) mod N] <- A[j];
        j <- (j - n) mod N
    A[(i + n) mod N] <- temp;

    Note que bien que nous avons deux boucles imbriquées, chaque élément est déplacé exactement une fois, et nous utilisons O(1) de l'espace. Un exemple d'une mise en œuvre en Java:

    public static int gcd(int a, int b) {
    while(b != 0) {
        int c = a;
        a = b;
        b = c % a;
    }
    return a;
}

public static void shift_array(int[] A, int n) {
    int N = A.length;
    n %= N;
    if(n < 0)
        n = N + n;
    int d = gcd(N, n);
    for(int i = 0; i < d; i++) {
        int temp = A[i];
        for(int j = i - n + N; j != i; j = (j - n + N) % N)
            A[(j + n) % N] = A[j];
        A[i + n] = temp;
    }
}
    InformationsquelleAutor SomeStrangeUser
  2. 2

    Ici est très facile de l'algorithme, avec O(1) de l'Espace en O(n)

    Algorithme

    • Inverse de la matrice de 0 à n (numberOfPositions) positions
    • Inverse de la matrice de n+1 à la longueur du tableau - 1 positions
    • Inverse le tableau entier de 0 à length - 1 positions

     public class ArrayRotator {

 private final int[] target;
 private final int length;

 public ArrayRotator(int[] seed) {
    this.target = seed;
    this.length = seed.length;
 }

 public void rotateInline(int numberOfPositions) {
    reverse(0, numberOfPositions);
    reverse(numberOfPositions + 1, length-1);       
    reverse(0, length-1);
 }

 private void reverse(int start, int end) {
    for (int i = start; i <= (start + end)/2; i++) {
        swap(i, start + end - i);
    }
 }

 private void swap(int first, int second) {
    int temp = this.target[second];
    this.target[second] = this.target[first];
    this.target[first] = temp;
 }
}


    Par exemple, disons que le tableau est [1,2,3,4] et n est 2

    Après la première étape, vous vous retrouvez [2,1,3,4]

    Après Étape deux, vous vous retrouvez [2,1,4,3]

    Après Étape trois, vous vous retrouvez [3,4,1,2]

    InformationsquelleAutor craftsmannadeem
  3. 1

    Vous pouvez changer les données par l'itération et de la copie, ce sera en O(n). Une autre approche consiste à créer un List de mise en œuvre qui enveloppe votre tableau et s'expose comme étant circulaire décalé. Cela avait l'avantage que le décalage est paresseusement fait quand get ou d'itération est effectuée.

    InformationsquelleAutor Steve Kuo
  4. 1

    Je voudrais passer 1 élément à la fois en place, à l'aide d'une seule variable temporaire pour contenir l'élément, tout en déplaçant les éléments 1, place le long de chaque. Je ne puis répétez cette n fois pour obtenir n changements.

    public static void main( String[] args ) {
    int[] array = {1,2,3,4,5,6,7,8};
    leftShift( array, 3);
    System.out.println( Arrays.toString( array));
}

public static void leftShift(int[] array, int n) {
    for (int shift = 0; shift < n; shift++) {
        int first = array[0];
        System.arraycopy( array, 1, array, 0, array.length - 1 );
        array[array.length - 1] = first;
    }
}

    De sortie:

    [4, 5, 6, 7, 8, 1, 2, 3]

    Pas trop inefficaces, comme System.arraycopy() est hautement optimisé.

    InformationsquelleAutor Bohemian
  5. 1

    Une autre alternative serait d'envelopper votre propre structure, qui comprend le tableau et l'indice de zéro virtuel.

    InformationsquelleAutor ddyer
  6. 1

    Je ne les croyons que System.arraycopy serait en fait il suffit de prendre l'ensemble de vos données d'un tableau et le mettre dans un autre de la même longueur juste déplacé.

    De toute façon de penser à ce problème est tout à fait intéressant de la tâche. La seule Solution que je pouvais penser pour le moment est de la merde un par un.
    Sans l'aide d'un autre Tableau, il devrait ressembler à cela:

    for(int i = 0; i < shift;i++)
        {
            tmp = array[0];
            for(int j = 0;j<array.length-1;j++)
                array[j]=array[j+1];
            array[array.length-1]=tmp;
        }

    pour les Tableaux de plus de 30 points mais il est plus efficace d'utiliser ce:

    for (int i = 0; i < shift; i++) {
            tmp = array[0];
            System.arraycopy( array, 1, array, 0, array.length - 1 );
            array[array.length - 1] = tmp;
        }

    Mais pour les grands ensembles et de grand changement qui sont proches de la taille de la matrice ainsi que pour de courts tableaux et les petites variations de cette méthode gagne la course:

        int[] array2 = new int[shift];
    for (int i = 0; i < shift; i++)
    {
        array2[i] = array[i];
    }
    System.arraycopy(array, shift, array, 0, array.length - shift);
    for (int i = array.length - shift; i < array.length; i++)
    {
        array[i] = array2[shift + i - array.length];
    }

    J'ai testé qu'avec un peu de la taille des matrices et des changements Voici les résultats pour 

        int[] array = new int[100000];
    int shift = 99999;

    en nanosecondes:
    1ère méthode:5663109208
    2ème méthode:4047735536
    3ème méthode:6085690
    Donc, vous devriez vraiment utiliser la 3ème méthode. Hope qui aide

    InformationsquelleAutor Walter Lars Lee
  7. 0
    for (int i = 0; i < n; i++)
    array[array.length - n + i] = array[i];
for (int i = 0; i < array.length - n; i++)
    array[i] = array[i + n];
    • Qui ne peux pas changer tout cela.
    • Yep, je n'ai pas vu la "circulaire" de la partie. Fixe maintenant.
    InformationsquelleAutor Zong
  9. 0

    Peut-être un vieux post.. mais voici ma solution (où A est évidemment le tableau et K le nombre de postes).

    public int[] solution(int[] A, int K){
    int[] result = new int[A.length];

    for (int i = 0; i<A.length; i++){
        result[(i+K)%A.length] = A[i];
    }
    return result;
}
    InformationsquelleAutor gipinani
  10. 0

    Java 8 version:

    public class Sample {
   public static void main(String[] args) {
     int[] answer = solution(new int[] {1,2,3,4}, 2);
     Arrays.stream(answer).forEach(System.out::print);
   }

   public static int[] solution(int[] A, int K) {
     List<Integer> numbers = 
     IntStream.of(A).boxed().collect(Collectors.toList());
     Collections.rotate(numbers, K);
     return numbers.stream().mapToInt(n -> n).toArray();
  }
}
    InformationsquelleAutor Joanne Agustin
  11. -1

    Comment à ce sujet?

        //Left shift the array in O(n) with O(1) space.

public static void leftShift(int[] array, int n) {
    int temp;
    int len = array.length;
    for (int i = 0; i < n; i++) {
        temp = array[len - n + i];
        array[len - n + i] = array[i];
        array[i] = array[n + i];
        array[n + i] = temp;
    }
}
    InformationsquelleAutor Bhumik Thakkar