¿Cómo invierto una matriz int en Java?

238

Estoy tratando de revertir una matriz int en Java.

Este método no invierte la matriz.

for(int i = 0; i < validData.length; i++)
{
    int temp = validData[i];
    validData[i] = validData[validData.length - i - 1];
    validData[validData.length - i - 1] = temp;
}

¿Qué tiene de malo?

MichaelScott
fuente
31
Veo lo que hice mal. Debe ser validData.length / 2. De lo contrario, se revertirá y luego se revertirá.
MichaelScott
44
Consulte en.wikipedia.org/wiki/In-place_algorithm que contiene una descripción de la versión correcta de este algoritmo.
Dean Povey el

Respuestas:

284

Para invertir una matriz int, intercambia elementos hacia arriba hasta llegar al punto medio, de esta manera:

for(int i = 0; i < validData.length / 2; i++)
{
    int temp = validData[i];
    validData[i] = validData[validData.length - i - 1];
    validData[validData.length - i - 1] = temp;
}

De la forma en que lo hace, intercambia cada elemento dos veces, por lo que el resultado es el mismo que la lista inicial.

3lectrologos
fuente
Y me gustaría poner validData.length / 2parte al exterior del ciclo for.
Jin Kwon
77
@Jin no lo haría. Solo ofusca el significado, y apuesto a que el compilador de optimización lo haría por usted de todos modos. De todos modos, no tiene sentido la micro-optimización hasta que tenga evidencia clara de la elaboración de perfiles de que es necesario / útil.
Nicu Stiurca
99
@ JinKwon Eso sería como hacer validData.length >> 1. Eso es equivalente y más rápido, pero confunde a muchos programadores y cualquier buen compilador lo hará automáticamente.
Justin
2
Solo debe hacer este cálculo una vez validData.length - i - 1y guardarlo en una variable.
¡¿Alguien puede sugerir una inversión sin la variable temporal!
sg28
303

Con Commons.Lang , simplemente podría usar

ArrayUtils.reverse(int[] array)

La mayoría de las veces, es más rápido y más seguro a prueba de errores apegarse a bibliotecas fácilmente disponibles que ya han sido probadas por la unidad y probadas por el usuario cuando se ocupan de su problema.

Manur
fuente
3
Hubiera preferido que devolviera la matriz invertida (aprobada) para un estilo funcional.
Laurent G
2
@ laurent-g para ser justos: revertir la matriz de esta manera es más eficiente en la memoria, lo que probablemente sea la razón por la que lo hicieron de esta manera.
Sirmyself
44
Mi punto no era la copia o no copiar. Mi mensaje dice "(aprobado)" para ser devuelto (después de ser revertido), por lo que podría pasarse en una expresión, sin necesidad de una declaración separada.
Laurent G
52
public class ArrayHandle {
    public static Object[] reverse(Object[] arr) {
        List<Object> list = Arrays.asList(arr);
        Collections.reverse(list);
        return list.toArray();
    }
}
Tarik
fuente
11
Por supuesto que lo hará. Una lista solo puede contener objetos, no primitivas, por lo que todas las primitivas ( ints en este caso) se envuelven en sus respectivos contenedores ( Integers en este caso) y se colocan en la lista. Ya ves, los Integers son objetos. @Tom
11684
66
Cuidado: si no me equivoco, la matriz original se modifica. Para que quede claro, es posible que desee no devolver nada.
Andrea Zilio
3
@ 11684 Sí, las listas genéricas solo pueden contener objetos. Pero el método exceptúa una matriz. Las matrices pueden contener primitivas. Por int[]lo tanto, es diferente de Integer[]. Inténtelo: Integer[] array = new int[5]. Obtendrás un error de compilación. Es por eso que la Arraysclase Java define un montón de métodos para trabajar con matrices primitivas. Intentar pasar un int[]método anterior dará como resultado algo así The method reverse(Object[]) in the type MakeSimple is not applicable for the arguments (int[]). @Filip: un algoritmo in situ utiliza menos memoria y se ejecuta más rápido.
Brian McCutchon
3
@Andrea En realidad, no lo es. La lista devuelta por Arrays.asList()no hace referencia a la matriz original, ni la matriz devuelta. Ese es uno de los problemas con este método: utiliza el triple de memoria y triplica el trabajo como un algoritmo in situ.
Brian McCutchon
44
Este método en sí podría funcionar, pero uno simplemente no puede pasar un int[]argumento a este método ( "tipos incompatibles: int [] no se puede convertir en Object []" ).
MC Emperor
47
Collections.reverse(Arrays.asList(yourArray));

java.util.Collections.reverse()puede invertir java.util.Listsy java.util.Arrays.asList()devuelve una lista que envuelve la matriz específica que le pasa, por yourArraylo tanto, se invierte después de la invocación de Collections.reverse().

El costo es solo la creación de un objeto List y no se requieren bibliotecas adicionales.

Se ha presentado una solución similar en la respuesta de Tarik y sus comentaristas, pero creo que esta respuesta sería más concisa y más fácil de analizar.

escitalopram
fuente
15
Para matrices de objetos, esta es una buena solución. Pero no funciona para matrices de primitivas. P.ej. pasar un int[]a asList(...)no devolverá un List<Integer>, sino un List<int[]>, que contiene un elemento. Hay AFAICS no hay una forma simple incorporada para convertir una int[]a una Integer[].
Martin Rust
44
Esto no funcionará con matrices primitivas ... las colecciones dosnt devuelven un valor, por lo que ahora tiene una matriz inútil como una lista en la memoria
NightSkyCode
@MartinRust Java 8+: Arrays.stream(arr).boxed().collect(Collectors.toList())oArrays.stream(arr).boxed().toArray(Integer[]::new)
Simon Forsberg
39

Creo que es un poco más fácil seguir la lógica del algoritmo si declara variables explícitas para realizar un seguimiento de los índices que está intercambiando en cada iteración del bucle.

public static void reverse(int[] data) {
    for (int left = 0, right = data.length - 1; left < right; left++, right--) {
        // swap the values at the left and right indices
        int temp = data[left];
        data[left]  = data[right];
        data[right] = temp;
    }
}

También creo que es más legible hacer esto en un ciclo while.

public static void reverse(int[] data) {
    int left = 0;
    int right = data.length - 1;

    while( left < right ) {
        // swap the values at the left and right indices
        int temp = data[left];
        data[left] = data[right];
        data[right] = temp;

        // move the left and right index pointers in toward the center
        left++;
        right--;
    }
}
Bill el lagarto
fuente
El intercambio de la vieja escuela parece más fácil, pero sí, cuando se trata de valores de índice de matriz a la izquierda, a la derecha, ... será útil para la depuración, si corresponde
Srinath Ganesh
También puede agregar 'public static void swap (int [] data, int index1, int index2) {...}' y ​​usarlo desde 'reverse' de esta manera: swap (data, left, right).
pm_
13

Aquí ya hay muchas respuestas, principalmente enfocadas en modificar la matriz en el lugar. Pero en aras de la exhaustividad, aquí hay otro enfoque que utiliza secuencias de Java para preservar la matriz original y crear una nueva matriz inversa:

    int[] a = {8, 6, 7, 5, 3, 0, 9};
    int[] b = IntStream.rangeClosed(1, a.length).map(i -> a[a.length-i]).toArray();
Patrick Parker
fuente
10

Con guayaba:

Collections.reverse(Ints.asList(array));
ZhekaKozlov
fuente
44
¡Esto es brillante! Corto y efectivo. Como todos los asListmétodos, crea una vista que escribe directamente en la matriz de respaldo (primitiva). Creo que el votante negativo pensó erróneamente que esto devolvió una lista en caja o algo así.
Luke Usherwood
@LukeUsherwood presumiblemente todavía habrá algo de sobrecarga del boxeo y el desempaquetado al llamar a get y set en cada elemento. Pero estoy de acuerdo con usted en que esta es una solución brillante.
Patrick Parker
De hecho, vale la pena tenerlo en cuenta. No creo que sea un gran problema en la mayoría de los códigos con los que trabajo personalmente: nuestras áreas "calientes" están bien definidas, el resto es un tipo de "código de pegamento". Al mismo tiempo, soy consciente de que la pérdida de memoria también crea un costo "oculto" adicional que los perfiladores no atribuyen a la función real.
Luke Usherwood
@LukeUsherwood todavía devuelve una lista en caja en lugar de una matriz
primaria
2
@AnthonyJClink No estoy seguro de a qué se refiere "it", pero la utilidad JDK Collections.reversees un método nulo. Esto opera en el lugar en una clase interna de Guava que envuelve un int[](ya que nunca almacena una lista de cuadros en caja Integer, no llamaría a la clase una "lista en caja", sino más bien una "Vista de lista de una matriz"). Pero sí, funciona a través de una interfaz que pasa Integerobjetos, por lo que esto crearía una gran cantidad de abandono de objetos temporales y boxeo como se mencionó. Pruebe una IntStreamo una biblioteca de colecciones primitivas donde el rendimiento es importante. (Trove, Koloboke, Eclipse Collections, ...)
Luke Usherwood
10

En el caso de Java 8 , también podemos utilizar IntStreampara invertir la matriz de enteros como:

int[] sample = new int[]{1,2,3,4,5};
int size = sample.length;
int[] reverseSample = IntStream.range(0,size).map(i -> sample[size-i-1])
                      .toArray(); //Output: [5, 4, 3, 2, 1]
akhil_mittal
fuente
7

Simple para loop!

for (int start = 0, end = array.length - 1; start <= end; start++, end--) {
    int aux = array[start];
    array[start]=array[end];
    array[end]=aux;
}
Apetrei Ionut
fuente
44
En el futuro, informe al autor de la pregunta específicamente qué hizo incorrectamente y qué hizo correctamente.
Kartik Chugh
1
cambiar start <= endastart < end
Leonard Pauli
5

Esto te ayudara

int a[] = {1,2,3,4,5};
for (int k = 0; k < a.length/2; k++) {
    int temp = a[k];
    a[k] = a[a.length-(1+k)];
    a[a.length-(1+k)] = temp;
}
Krishna Kumar Chourasiya
fuente
5
for(int i=validData.length-1; i>=0; i--){
  System.out.println(validData[i]);
 }
Deepak Singh
fuente
Desafortunadamente, esta es la respuesta más limpia disponible aquí, porque cada desarrollador sabrá cómo hacerlo y no requiere la instalación de paquetes extendidos.
HoldOffHunger
5

Así es como lo resolvería personalmente. La razón detrás de la creación del método parametrizado es permitir que se ordene cualquier matriz ... no solo sus enteros.

Espero que obtengas algo de eso.

@Test
public void reverseTest(){
   Integer[] ints = { 1, 2, 3, 4 };
   Integer[] reversedInts = reverse(ints);

   assert ints[0].equals(reversedInts[3]);
   assert ints[1].equals(reversedInts[2]);
   assert ints[2].equals(reversedInts[1]);
   assert ints[3].equals(reversedInts[0]);

   reverseInPlace(reversedInts);
   assert ints[0].equals(reversedInts[0]);
}

@SuppressWarnings("unchecked")
private static <T> T[] reverse(T[] array) {
    if (array == null) {
        return (T[]) new ArrayList<T>().toArray();
    }
    List<T> copyOfArray = Arrays.asList(Arrays.copyOf(array, array.length));
    Collections.reverse(copyOfArray);
    return copyOfArray.toArray(array);
}

private static <T> T[] reverseInPlace(T[] array) {
    if(array == null) {
        // didn't want two unchecked suppressions
        return reverse(array);
    }

    Collections.reverse(Arrays.asList(array));
    return array;
}
AnthonyJClink
fuente
2
No resuelve el problema original usando primitivas.
Melinda Green
Hay muchas formas de convertir prims en objetos. Siempre recomiendo evitar los prims siempre que sea posible en Java y también creo que debería alentarse.
AnthonyJClink
Convertir una matriz de primitivas de longitud desconocida en una matriz podría ser una muy mala idea, especialmente si se realiza sin darse cuenta. Java no es Smalltalk. Las primitivas son parte del lenguaje y tienen su lugar. No importa si no nos gustan, debemos aceptarlos y usarlos cuando sea apropiado.
Melinda Green
1
En realidad, no necesita copiar la matriz, solo Collections.reverse(asList(arraytoReverse)); return arrayToReverse;. asListes solo un contenedor alrededor de la matriz, por lo que la matriz original se invierte.
Radiodef
3

Su programa solo funcionará length = 0, 1. Puedes probar :

int i = 0, j = validData.length-1 ; 
while(i < j)
{
     swap(validData, i++, j--);  // code for swap not shown, but easy enough
}
fastcodejava
fuente
3
Quizás quiso decir swap como pseudocódigo para un intercambio en línea en lugar de una llamada a método, pero si no, eso no funcionará. Java pasa por referencia, por lo que no es posible escribir un método de intercambio para variables.
Dean Povey
Me refería a cualquier forma en que puedas intercambiar v [i] y v [j]. Soy consciente de cómo funcionan las llamadas a métodos en Java. Para el método, puede hacer algo como intercambiar (v, i ++, j--);
fastcodejava
1
Dean, la matriz validData es un objeto, pasado por referencia, por lo que el método swap () funcionará perfectamente.
Gaël Oberson
3

Si trabaja con datos que son más primitivos (es decir, char, byte, int, etc.), puede realizar algunas divertidas operaciones XOR.

public static void reverseArray4(int[] array) {
    int len = array.length;
    for (int i = 0; i < len/2; i++) {
        array[i] = array[i] ^ array[len - i  - 1];
        array[len - i  - 1] = array[i] ^ array[len - i  - 1];
        array[i] = array[i] ^ array[len - i  - 1];
    }
}
AbsolutoAzul
fuente
1
Demasiado lindo para usar en el código de producción pero divertido de todos modos. Para obtener la máxima simpatía, use la operación% = de esta manera: array [i]% = array [len - i - 1], etc.
Melinda Green
Similar, pero un poco más corto:for (int m = x.length, i = --m / 2; ++i <= m;) { x[i] ^= x[m - i]; x[i] ^= x[m - i] ^= x[i]; }
Thomas Mueller
2

Es más eficiente simplemente iterar la matriz hacia atrás.

No estoy seguro de si la solución de Aaron hace esto vi esta llamada Collections.reverse(list);¿Alguien sabe?

Nick Strupat
fuente
Iterar hacia atrás sobre la matriz requiere una nueva matriz. Me gusta la solución publicada anteriormente que hace la inversión en línea sin crear una nueva matriz.
mmcdole
1
@Simucal ¿por qué crear una nueva matriz? Simplemente repítelo al revés.
Trejkaz
2
public void getDSCSort(int[] data){
        for (int left = 0, right = data.length - 1; left < right; left++, right--){
            // swap the values at the left and right indices
            int temp = data[left];
            data[left]  = data[right];
            data[right] = temp;
        }
    }
amicos
fuente
1
public void display(){
  String x[]=new String [5];
  for(int i = 4 ; i > = 0 ; i-- ){//runs backwards

    //i is the nums running backwards therefore its printing from       
    //highest element to the lowest(ie the back of the array to the front) as i decrements

    System.out.println(x[i]);
  }
}
programador fantasma
fuente
1
Sí, he intentado lo mismo y el código claro junto con la salida es int [] a = {1,3,5,2,6,7}; for (int i = a.length-1; i> = 0; i--) {System.out.print (a [i] + "");} `invertirá la matriz del último índice al primer índice
Rocket_03
1

¿No sería así mucho más improbable que se cometieran errores?

    int[] intArray = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    int[] temp = new int[intArray.length];
    for(int i = intArray.length - 1; i > -1; i --){
            temp[intArray.length - i -1] = intArray[i];
    }
    intArray = temp;
ModDL
fuente
1

Solución con o (n) complejidad de tiempo y o (1) complejidad de espacio.

void reverse(int[] array) {
    int start = 0;
    int end = array.length - 1;
    while (start < end) {
        int temp = array[start];
        array[start] = array[end];
        array[end] = temp;
        start++;
        end--;
    }
}
user11016
fuente
Para su información, esto se puede simplificar en un complejo de bucle: for (int start = 0, end = array.length - 1; start < end; start++, end--) { ... }.
Tim Cooke
1

2 formas de revertir una matriz.

  1. Usando el bucle For e intercambia los elementos hasta el punto medio con una complejidad temporal de O (n / 2).

    private static void reverseArray() {
    int[] array = new int[] { 1, 2, 3, 4, 5, 6 };
    
    for (int i = 0; i < array.length / 2; i++) {
        int temp = array[i];
        int index = array.length - i - 1;
        array[i] = array[index];
        array[index] = temp;
    }
    System.out.println(Arrays.toString(array));

    }

  2. Uso de la función integrada (Collections.reverse ())

    private static void reverseArrayUsingBuiltInFun() {
    int[] array = new int[] { 1, 2, 3, 4, 5, 6 };
    
    Collections.reverse(Ints.asList(array));
    System.out.println(Arrays.toString(array));

    }

    Salida: [6, 5, 4, 3, 2, 1]

Sameer Shrestha
fuente
3
¿Qué es Ints?
CodingNow
@CodingNow es una de las clases de ayuda de la utilidad Guava - mira aquí
mrec
1
    public static void main(String args[])    {
        int [] arr = {10, 20, 30, 40, 50}; 
        reverse(arr, arr.length);
    }

    private static void reverse(int[] arr,    int length)    {

        for(int i=length;i>0;i--)    { 
            System.out.println(arr[i-1]); 
        }
    }
Kalidindi Prashanth
fuente
1

Hay algunas respuestas excelentes arriba, pero así es como lo hice:

public static int[] test(int[] arr) {

    int[] output = arr.clone();
    for (int i = arr.length - 1; i > -1; i--) {
        output[i] = arr[arr.length - i - 1];
    }
    return output;
}
Ahmad Dalao
fuente
0

a continuación se muestra el programa completo para ejecutar en su máquina.

public class ReverseArray {
    public static void main(String[] args) {
        int arr[] = new int[] { 10,20,30,50,70 };
        System.out.println("reversing an array:");
        for(int i = 0; i < arr.length / 2; i++){
            int temp = arr[i];
            arr[i] = arr[arr.length - i - 1];
            arr[arr.length - i - 1] = temp;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }   
    }
}

Para los programas en matriz que usan matrices, esta será la buena fuente Vaya a través del enlace.

Mdhar9e
fuente
0

Usando la solución XOR para evitar la variable temporal, su código debería verse como

for(int i = 0; i < validData.length; i++){
    validData[i] = validData[i] ^ validData[validData.length - i - 1];
    validData[validData.length - i - 1] = validData[i] ^ validData[validData.length - i - 1];
    validData[i] = validData[i] ^ validData[validData.length - i - 1];
}

Vea este enlace para una mejor explicación:

http://betterexplained.com/articles/swap-two-variables-using-xor/

vikarjramun
fuente
0
private static int[] reverse(int[] array){
    int[] reversedArray = new int[array.length];
    for(int i = 0; i < array.length; i++){
        reversedArray[i] = array[array.length - i - 1];
    }
    return reversedArray;
} 
Stuart Clark
fuente
44
Considere agregar una explicación a su respuesta. Las respuestas de solo código no explican nada.
rgettman
0

Aquí hay una implementación simple, para invertir la matriz de cualquier tipo , más soporte completo / parcial .

import java.util.logging.Logger;

public final class ArrayReverser {
 private static final Logger LOGGER = Logger.getLogger(ArrayReverser.class.getName());

 private ArrayReverser () {

 }

 public static <T> void reverse(T[] seed) {
    reverse(seed, 0, seed.length);
 }

 public static <T> void reverse(T[] seed, int startIndexInclusive, int endIndexExclusive) {
    if (seed == null || seed.length == 0) {
        LOGGER.warning("Nothing to rotate");
    }
    int start = startIndexInclusive < 0 ? 0 : startIndexInclusive;
    int end = Math.min(seed.length, endIndexExclusive) - 1;
    while (start < end) {
        swap(seed, start, end);
        start++;
        end--;
    }
}

 private static <T> void swap(T[] seed, int start, int end) {
    T temp =  seed[start];
    seed[start] = seed[end];
    seed[end] = temp;
 }  

}

Aquí está la prueba de unidad correspondiente

import static org.hamcrest.CoreMatchers.is;
import static org.junit.Assert.assertThat;

import org.junit.Before;
import org.junit.Test;

public class ArrayReverserTest {
private Integer[] seed;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{1,2,3,4,5,6,7,8};
}

@Test
public void wholeArrayReverse() {
    ArrayReverser.<Integer>reverse(seed);
    assertThat(seed[0], is(8));
}

 @Test
 public void partialArrayReverse() {
    ArrayReverser.<Integer>reverse(seed, 1, 5);
    assertThat(seed[1], is(5));
 }
}
artesano
fuente
0

Esto es lo que se me ocurrió:

// solution 1 - boiler plated 
Integer[] original = {100, 200, 300, 400};
Integer[] reverse = new Integer[original.length];

int lastIdx = original.length -1;
int startIdx = 0;

for (int endIdx = lastIdx; endIdx >= 0; endIdx--, startIdx++)
   reverse[startIdx] = original[endIdx];

System.out.printf("reverse form: %s", Arrays.toString(reverse));

// solution 2 - abstracted 
// convert to list then use Collections static reverse()
List<Integer> l = Arrays.asList(original);
Collections.reverse(l);
System.out.printf("reverse form: %s", l);
Solución simple
fuente
0

Hay dos formas de tener una solución para el problema:

1. Invierta una matriz en el espacio.

Paso 1. Intercambie los elementos al inicio y al final del índice.

Paso 2. Incremente el índice inicial disminuya el índice final.

Paso 3. Itere el Paso 1 y el Paso 2 hasta el índice inicial <índice final

Para esto, la complejidad del tiempo será O (n) y la complejidad del espacio será O (1)

El código de muestra para invertir una matriz en el espacio es como:

public static int[] reverseAnArrayInSpace(int[] array) {
    int startIndex = 0;
    int endIndex = array.length - 1;
    while(startIndex < endIndex) {
        int temp = array[endIndex];
        array[endIndex] = array[startIndex];
        array[startIndex] = temp;
        startIndex++;
        endIndex--;
    }
    return array;
}

2. Invierta una matriz utilizando una matriz auxiliar.

Paso 1. Cree una nueva matriz de tamaño igual a la matriz dada.

Paso 2. Inserte elementos en la nueva matriz comenzando desde el índice inicial, desde la matriz dada comenzando desde el índice final.

Para esto, la complejidad temporal será O (n) y la complejidad espacial será O (n)

El código de muestra para invertir una matriz con matriz auxiliar es como:

public static int[] reverseAnArrayWithAuxiliaryArray(int[] array) {
    int[] reversedArray = new int[array.length];
    for(int index = 0; index < array.length; index++) {
        reversedArray[index] = array[array.length - index -1]; 
    }
    return reversedArray;
}

Además, podemos usar la API de colecciones de Java para hacer esto.

La API de colecciones usa internamente el mismo enfoque inverso en el espacio.

El código de muestra para usar la API de colecciones es como:

public static Integer[] reverseAnArrayWithCollections(Integer[] array) {
    List<Integer> arrayList = Arrays.asList(array);
    Collections.reverse(arrayList);
    return arrayList.toArray(array);
}
Karan Khanna
fuente
0
static int[] reverseArray(int[] a) {
     int ret[] = new int[a.length];
     for(int i=0, j=a.length-1; i<a.length && j>=0; i++, j--)
         ret[i] = a[j];
     return ret;
}
ZA Abbasi
fuente
0
 public static int[] reverse(int[] array) {

    int j = array.length-1;
    // swap the values at the left and right indices //////
        for(int i=0; i<=j; i++)
        {
             int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
           j--;
        }

         return array;
    }

      public static void main(String []args){
        int[] data = {1,2,3,4,5,6,7,8,9};
        reverse(data);

    }
Roshan Posakya
fuente