Java - la Rotation de la matrice de

Donc le but est de faire pivoter les éléments dans une rangée droite a fois.
Comme un exemple; si a==2, puis array = {0,1,2,3,4} deviendrait array = {3,4,0,1,2}

Voici ce que j'ai:

for (int x = 0; x <= array.length-1; x++){
    array[x+a] = array[x];
}

Toutefois, cela ne prend pas en compte lors de la [x+a] est plus grande que la longueur du tableau. J'ai lu que je devrais stocker ceux qui sont plus dans un autre Tableau mais, voyant que a est variable, je ne suis pas sûr que ce soit la meilleure solution.
Merci à l'avance.

Modulo est votre ami.
x < array.length est plus propre et plus conventionnel que x <= array.length-1.

InformationsquelleAutor | 2014-10-28

27

Ajouter un modulo tableau de la longueur de votre code:
```
//create a newArray before of the same size as array

//copy
for(int x = 0; x <= array.length-1; x++){
  newArray[(x+a) % array.length ] = array[x];
}
```
Vous devez également créer un nouveau Array de copie, de sorte que vous ne pas écraser les valeurs, que vous en aurez besoin plus tard.
- Cela a fonctionné parfaitement, merci beaucoup!
- Est-il une meilleure façon, sans avoir à utiliser le supplément de temp mémoire (variable newArray) ?
- Je suppose que vous aurez au moins besoin d'une variable pour stocker temporairement certaines valeurs. Il devrait être possible, mais le code serait beaucoup plus compliqué.
InformationsquelleAutor Sirko
12

Dans le cas où vous ne voulez pas de réinventer la roue (c'est peut-être un exercice mais il peut être bon à savoir), vous pouvez utiliser Collections.rotate.

Être conscient qu'il nécessite un tableau d'objets, pas de type de données primitif (sinon, vous allez swap tableaux eux-mêmes dans la liste).
```
Integer[] arr = {0,1,2,3,4};
Collections.rotate(Arrays.asList(arr), 2);
System.out.println(Arrays.toString(arr)); //[3, 4, 0, 1, 2]
```
- Je suis sûr que cela fonctionne très bien aussi, mais c'était un exercice 😉
InformationsquelleAutor user2336315
6

Arraycopy est une opération coûteuse, à la fois du temps et de la mémoire de sage.
La suite serait un moyen efficace pour faire pivoter une matrice, sans l'aide de l'espace supplémentaire (à la différence de la accepté de répondre lorsqu'un nouveau tableau est créé de la même taille).
```
public void rotate(int[] nums, int k) { //k = 2
    k %= nums.length;
    //{0,1,2,3,4}

    reverse(nums, 0, nums.length - 1); //Reverse the whole Array
    //{4,3,2,1,0}

    reverse(nums, 0, k - 1); //Reverse first part (4,3 -> 3,4)
    //{3,4,2,1,0}

    reverse(nums, k, nums.length - 1); //Reverse second part (2,1,0 -> 0,1,2)
    //{3,4,0,1,2}
}

public void reverse(int[] nums, int start, int end) {
    while (start < end) {
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
        start++;
        end--;
    }
}
```
- La complexité de cette méthode sera O(2n). Pas impressionnant
- Approche astucieuse, mais je crains que cet algorithme serait inefficace pour grand Tableau est que la complexité du temps est de 3 * O(n). Système.arraycopy() sur l'autre main est une méthode native qui va copier les éléments au niveau de la mémoire, il devrait être plus rapide pour les cas où votre groupe est grand.
- L'objectif de cette réponse a été de fournir une solution qui n'utilise pas d'espace supplémentaire, je devrais avoir été clair dans la réponse elle-même. (L'édition). @Ekansh Bien, je peux me tromper mais il me semble que l'inversion d'une matrice serait l'heure de prise d'effet de la complexité de O(N), le meilleur que vous pouvez obtenir pour faire pivoter le tableau comme il ne peut pas être une solution avec O(1). Arif conformément à ma connaissance 3*O(N) est toujours en O(N). Et Le Système.arraycopy() a également le même temps, la complexité de O(N).
InformationsquelleAutor A-patel-guy

Une autre façon est de la copie avec Système.arraycopy.

    int[] temp = new int[array.length];
    System.arraycopy(array, 0, temp, a, array.length - a);
    System.arraycopy(array, array.length-a, temp, 0, a);

InformationsquelleAutor dusky

1

Je pense que le moyen le plus rapide serait d'utiliser Système.arrayCopy() qui est originaire de la méthode:
```
int[] tmp = new int[a];
System.arraycopy(array, array.length - a, tmp, 0, a);
System.arraycopy(array, 0, array, a, array.length - a);
System.arraycopy(tmp, 0, array, 0, a);
```
Il réutilise aussi une matrice existante. Il peut être bénéfique dans certains cas.
Et le dernier avantage est temporaire taille de la matrice est moins que le tableau d'origine. De sorte que vous pouvez réduire l'utilisation de la mémoire lorsque a est petit.

InformationsquelleAutor ponomandr

Solution Java enveloppé dans une méthode:

public static int[] rotate(final int[] array, final int rIndex) {
    if (array == null || array.length <= 1) {
        return new int[0];
    }

    final int[] result = new int[array.length];
    final int arrayLength = array.length;

    for (int i = 0; i < arrayLength; i++) {
        int nIndex = (i + rIndex) % arrayLength;
        result[nIndex] = array[i];
    }
    return result;
}

InformationsquelleAutor realPK

De Gauche Tourner à sa très simple

Prendre la différence entre la longueur du tableau et le nombre de position de changement.

Par Exemple

int k = 2;
int n = 5;

int diff = n - k;

int[] array = {1, 2, 3, 4, 5};
int[] result = new int[array.length];
System.arraycopy(array, 0, result, diff, k);
System.arraycopy(array, k, result, 0, diff);

//imprimer la sortie

InformationsquelleAutor manishkummar

0

Question : https://www.hackerrank.com/challenges/ctci-array-left-rotation

Solution :
C'est de cette façon que j'ai essayé arrayLeftRotation méthode de complexité o(n)
- en boucle la fois à partir d'indice k de (longueur-1 )
- 2ème fois pour les 0 à kth indice
  
  public static int[] arrayLeftRotation(int[] a, int n, int k) {
  
  int[] resultArray = new int[n];
  
  int arrayIndex = 0;
  
  //première n-k indices seront remplies dans cette boucle
  
  for(int i = k ; i
  resultArray[arrayIndex] = a[i];
  
  arrayIndex++;
  
  }
  
  //2e k indices seront remplies dans cette boucle
  
  for(int j=arrayIndex ; j<(arrayIndex+k); j++){
  
  resultArray[j]=a[j-(n-k)];
  
  }
  
  retour resultArray;
  
  }
InformationsquelleAutor user3847870

package com.array.orderstatistics;

import java.util.Scanner;

public class ArrayRotation {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int r = scan.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scan.nextInt();
        }
        scan.close();

        if (r % n == 0) {
            printOriginalArray(a);
        } else {
            r = r % n;
            for (int i = 0; i < n; i++) {
                b[i] = a[(i + r) < n ? (i + r) : ((i + r) - n)];
                System.out.print(b[i] + " ");
            }
        }
    }

    private static void printOriginalArray(int[] a) {
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }

}

InformationsquelleAutor Yuvaraj Ram

Dans ruby rotation d'un tableau peut être possible dans une ligne.

def array_rotate(arr)
   i, j = arr.length - 1, 0
   arr[j],arr[i], i, j = arr[i], arr[j], i - 1, j + 1 while(j<arr.length/2)
   puts "#{arr}"
end

InformationsquelleAutor Arjun

Question : Rotation de la table donnée une distance spécifique .
Méthode 1 :
Mettez l'int tableau ArrayList. Ensuite, l'utilisation des Collections.tourner(liste,de la distance).

class test1 {
    public static void main(String[] args) {

        int[] a = { 1, 2, 3, 4, 5, 6 };

        List<Integer> list = Arrays.stream(a).boxed().collect(Collectors.toList());

        Collections.rotate(list, 3);
        System.out.println(list);//[4, 5, 6, 1, 2, 3]

    }//main
}

InformationsquelleAutor Soudipta Dutta

Complexité temporelle = O(n)

Espace Complexité = O(1)

L'algorithme commence avec le premier élément du tableau (newValue) et le place à sa position après la rotation (newIndex). L'élément qui est à la newIndex devient oldValue. Après cela, oldValue et newValue sont inversés.

Cette procédure se répète longueur de temps.

L'algorithme fondamentalement rebondit autour de la matrice de mise en place de chaque élément à sa nouvelle position.

unsigned int computeIndex(unsigned int len, unsigned int oldIndex, unsigned int times) {
    unsigned int rot = times % len;
    unsigned int forward = len - rot;

    //return (oldIndex + rot) % len; //rotating to the right
    return (oldIndex + forward) % len; //rotating to the left
}

void fastArrayRotation(unsigned short *arr, unsigned int len, unsigned int rotation) {
    unsigned int times = rotation % len, oldIndex, newIndex, length = len;
    unsigned int setIndex = 0;
    unsigned short newValue, oldValue, tmp;

    if (times == 0) {
        return;
    }

    while (length > 0) {
        oldIndex = setIndex;
        newValue = arr[oldIndex];
        while (1) {
            newIndex = computeIndex(len, oldIndex, times);
            oldValue = arr[newIndex];
            arr[newIndex] = newValue;

            length--;

            if (newIndex == setIndex) { //if the set has ended (loop detected)
                break;
            }

            tmp = newValue;
            newValue = oldValue;
            oldValue = tmp;

            oldIndex = newIndex;
        }
        setIndex++;
    }
}

InformationsquelleAutor Vlad

Vous devez vous connecter pour publier un commentaire.