Cómo girar una matriz de enteros por i veces utilizando swap función sólo en el tiempo lineal.

  • Por favor, pon tu pregunta un poco. ¿Qué dimensión tiene la matriz? ¿Qué entiende usted por «rotación de una matriz»? Dar un ejemplo de entrada y de salida. Considere el uso de signos de puntuación y las letras mayúsculas donde corresponda.
  • Lo has intentado? ¿Cómo que no funciona? IOW, hay que probar primero antes de ayudar (no vamos a escribir formulario)
  • supongamos matriz de entrada es {1,2,3,4,5} matriz de salida después de una rotación es {5,1,2,3,4}.
  • para girar veces lo podemos hacer en o(n^2) veces, pero quiero o(n) complejidad.
  • no sé por qué alguien votado en mi respuesta, pero es posible con un pequeño algoritmo O(n)! Ver mi respuesta para más detalles.
  • Se debe indicar que la operación debe ser realizada in place o O(1) espacio, de lo contrario, sólo tiene que utilizar otro bloque de memoria, hacer 3 memmoves.
  • La dimensión de la matriz es irrelevante. Lo que se quiere aquí es un algoritmo o método, o una función, pero ninguno de esos funciona con cualquier valor de N.

InformationsquelleAutor algo-geeks | 2010-12-16

20 Comentarios

  1. 46

    Usted puede hacer esto en el tiempo lineal mediante el uso de un reverse() ayudante.

    //rotate array of size=size, by n positions
    void rotate(int array[], int size, int n)
    {
      //reverse array[0...size-1]
      reverse(array, 0, size-1);
    
      //reverse A[0...n-1]
      reverse(array, 0, n-1);
    
      //reverse A[n...size-1]
      reverse(array, n, size-1);
    }
    
    //reverse elements in the array[pos_from ... pos_to]
    void reverse(int array[], int pos_from, int pos_to)
    {
       ...
    }
    

    La aplicación de reverse(int array[], int pos_from, int pos_to) el uso de swaps se deja como ejercicio para el lector. Sugerencia: Esto se puede hacer en el tiempo lineal.

  2. 18

    Digamos que tenemos una función llamada arr_reverse(arr,i,j) que invierte los elementos de la matriz arr entre el índice de i y j el uso de la swap función.

    Ejemplo:

    arr = {1,2,3,4,5} 
    i = 0
    j = 2
    

    a continuación, la función devolverá:

    {3,2,1,4,5} 
     ^^^^^
    

    La implementación de esta función es muy sencillo y es O(N).

    Ahora vamos a utilizar esta función en la rotación de la matriz.

    arr     = {1,2,3,4,5} //input array
    k       = 2 //amount of right rotation
    result  = {4,5,1,2,3} //expected result 
    l       = 5 //length of array.
    
    Step 1: Call arr_reverse(arr,l-k,l-1) which is arr_reverse(arr,3,4)
    we get {1,2,3,5,4} 
                  ^^^
    
    Step 2: Call arr_reverse(arr,0,l-k-1) which is arr_reverse(arr,0,2)
    we get {3,2,1,5,4}
            ^^^^^     
    
    Step 3: Call arr_reverse(arr,0,l-1) which is arr_reverse(arr,0,4)
    we get {4,5,1,2,3} 
            ^^^^^^^^^
    

    Todo el proceso hace uso de arr_reverse 3 veces, lo que es O(N)

    • Creo que ha cometido un error tipográfico en el Paso 2 y 3 de su ejemplo, donde se muestra el resultado. Usted tiene el 4 y 5 volteado de lo que deberían ser.
    • Gracias por darse cuenta.
  3. 4

    Aquí una solución mejor, de una naturaleza diferente de los demás. Se involucra menos de la matriz de swaps de que los otros. Python:

    import fractions
    # rotates an array in-place i positions to the left, in linear time
    def rotate(arr,i):
        n = len(arr)
        reps = fractions.gcd(n,i)
        swaps = n /reps
        for start in xrange(reps):
            ix = start
            tmp = arr[ix]
            for s in xrange(swaps-1):
                previx = ix
                ix = (ix + i) % n
                arr[previx] = arr[ix]
            arr[ix] = tmp
        return arr
    
  4. 1

    ingenua de un pseudocódigo aplicación:

    for (n = 0; n < i; n++) {
        for (j = array.length-1; j > n; j--)
            swap(j, j-1)
    }
    

    Repetidamente se mueve el último elemento a la parte delantera, parando antes de que se mueve nada previamente se trasladó a la parte delantera

    • he intentado mismo soln pero lo quiero en o(n)
    • Podría haber mencionado que en la pregunta, entonces, eh?
  5. 1

    Mejor uso directo y simple de la función, la complejidad N:

    int rotate(int* a,int DIM,int rn,int* b) {
        int i; //counter 
        for(i=0;i<DIM;i++){ //looping through the array
            b[(i+rn)%len]=a[i]; //copying the values in the b array=a shifted with rn(+ for right or - for left shifting
    }
    
  6. 1
    public int[] shift(int[] A, int K) {
        int N = A.length;
        if (N == 0)
            return A;
        int mid =  -K % N;
        if (mid < 0)
            mid += N;
        if (mid == 0)
            return A;
    
        reverseSubArray(A, 0 , mid - 1);
    
        reverseSubArray(A, mid , N - 1);
    
        reverseSubArray(A, 0 , N - 1);
    
        return A;
    }
    
    private void reverseSubArray(int[] A, int start , int end){
        int i = 0;
        int tmp;
        while (i < (end - start + 1) /2) {
            tmp = A[i + start];
            A[i + start] = A[end - i];
            A[end - i] = tmp;
            i++;
        }
    
    }
    

    Doug McIlroy es Handwaving Descripción

  7. 0

    por qué sólo la función de intercambio?

    O(n) en el tiempo y en el espacio:

    var rotateCount = 1;
    var arr = new Array(1,2,3,4,5,6,7,8,9,10);
    
    tmp = new Array(arr.length);
    for (var i = 0; i<arr.length; i++)
        tmp[(i+rotateCount)%arr.length]=arr[i];
    arr = tmp;
    
    alert(arr);
    
    • por qué voto?? Este código funciona!
    • Este código no funciona. Trate de rotateCount = 8, se produce: 9,10,2,3,4,5,6,7,8,1.
    • corregido el bug
    • Aún roto, prueba rotateCount = 3, que va a producir: 4,5,6,7,8,9,10,2,3,1.
    • También, usted realmente debería probar el código antes de publicarlo. Me tomó 3 segundos para probar esto y ver que no funciona.
  8. 0
    /* Q: How can we shift/rotate an array in place?
    A: "in place" means O(1) space complexity, so we need to do some trick
     */
    
    #include <iostream>
    #include <algorithm>
    using namespace std;
    
    void ArrayRotate(int a[], int n, int k)
    {
        if (n < 1 || k % n == 0 ) return;
    
        k %= n;
        if (k < 0) k += n;
    
        reverse(a, a+k);
        reverse(a+k, a+n);
        reverse(a, a+n);
    }
    
    void PrintArray(int a[], int n)
    {
        for ( int i = 0 ; i < n; ++i)
            cout << a[i] << " ";
        cout << endl;
    }
    
    int main()
    {
        int a[] = { 1, 2 , 3, 4, 5 };
        int n = sizeof(a)/sizeof (a[0]);
    
        PrintArray(a, n);
        ArrayRotate(a, n, 2);
        PrintArray(a, n);
    
        return 0;
    }
    /* Output:
    1 2 3 4 5
    3 4 5 1 2
     */
    
  9. 0

    utilizando sólo de intercambio, a continuación se presenta una implementación en C++

    template<class T>
    void rotate_array(std::vector<T> *array, int i) {
      int n = array->size();
      i = i % n;
      int gcd_n_i = gcd(i, n);
      for (int j = 0; j < gcd_n_i; j++) {
        T first_element = array->at(j);
        for (int k = j; (k + i) % n != j; k = (k + i) % n) {
          std::swap(array->at(k), array->at((k + i) % n));
        }
      }
    }
    

    Usted puede leer más acerca de esto en http://pointer-overloading.blogspot.in/2013/09/algorithms-rotating-one-dimensional.html

  10. 0
    void reverse_array(int a[], int start, int end){
    
        while(start < end){     
                int temp =  a[start];
                a[start] = a[end];
                a[end] = temp;
                start++;
                end--;
        }
    

    }

    void rotate_array(int a[], int pivot, int len){
        int i;
        /*Reverse the whole array */
        reverse_array(a, 0, len);
    
        /* Reverse from 0 to pivot and pivot to end */
        reverse_array(a,0, pivot);
        reverse_array(a,pivot+1,len);
    

    }

    • Esto es idéntico a la aceptación de la respuesta, que también llegó 3 años anteriores. 😉
  11. 0

    He aquí un pequeño fragmento de eso se trabaja en O(n), escrito en JavaScript.
    El keyconcept es, que siempre hay que trabajar con el elemento sustituido.

    function swap(arr, a, v) {
        var old = arr[a];
        arr[a] = v;
        return old;
    }
    
    function rotate(arr, n) {
        var length = arr.length;
        n = n % length;
        if(!n) return arr;
    
        for(var cnt = 0, 
                index = 0,
                value = arr[index],
                startIndex = index; 
            cnt < length; 
            cnt++) {
    
            //Calc next index
            var nextIndex = mapIndex(index, n, length);
    
            //Swap value with next
            value = swap(arr, nextIndex, value)
    
            if(nextIndex == startIndex) {
                startIndex = index = mapIndex(index, 1, length);
                value = arr[index];
            } else {
                index = nextIndex;
            }
        }
    
        return arr;
    }
    
    function mapIndex(index, n, length) {
        return (index - n + length) % length;
    }
    
    console.log(rotate([1,2,3,4,5,6,7,8,9], 5))
    console.log(rotate([1,2,3,4,5,6], 2))
    
  12. 0

    Un O(1) método de llevar a cabo esto, en python:

    class OffsetList(list):
        __slots__ = 'offset'
        def __init__(self, init=[], offset=-1):
            super(OffsetList, self).__init__(init)
            self.offset = offset
        def __getitem__(self, key):
            return super(OffsetList, self).__getitem__(key + self.offset)
        def __setitem__(self, key, value):
            return super(OffsetList, self).__setitem__(key + self.offset, value)
        def __delitem__(self, key):
            return super(OffsetList, self).__delitem__(key + self.offset)
        def index(self, *args):
            return super(OffsetList, self).index(*args) - self.offset
    

    Esto se basa en esta respuesta sobre el uso de un 1 lista basada en python.

    Esto tiene el ligero inconveniente de que si intenta índice de un elemento al final de la lista, se devolverá a los elementos de la (nueva) principio, y negativo indicies menor que el tamaño de menos el desplazamiento no funciona.

  13. 0

    aquí está mi respuesta usando js espero que esto ayude
    donde k es el número de rotaciones desea preforma

     var arrayRoatate=function(array,k){
        for(;k>0;k--) {
         var nextElementValue=undefined;
            for (var i = 0; i < array.length; i=i+2) {
                var nextElement = i + 1;
                if (nextElement >= array.length)
                    nextElement = nextElement - array.length;
                var tmp=array[i];
                if(nextElementValue!==undefined)
                    array[i]=nextElementValue
                nextElementValue=array[nextElement];
                array[nextElement]=tmp;
    
            }
        }
    return array;
    
  14. 0
    /*
     * To change this template, choose Tools | Templates
     * and open the template in the editor.
     */
    package rotateinlineartime;
    
    /**
     *
     * @author Sunshine
     */
    public class Rotator {
    
        void reverse(int a[], int n) {
            for (int i = 0; i <= n - 1; i++) {
                int temp;
                temp = a[i];
                a[i] = a[n - 1];
                a[n - 1] = temp;
                n--;
            }
    
            printArray(a);
        }
    
        void printArray(int a[]) {
            for (int i = 0; i < a.length; i++) {
                System.out.println(a[i]);
            }
        }
    }
    
  15. 0

    Para circular a la derecha de la rotación.

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int k = scan.nextInt() % n;
        int q = scan.nextInt();
        int arr[] = new int[n];
    
        for (int i = 0; i < n; i++) 
        {
            int a = i + k;
            int pos = (a < n) ? a : a - n;
            arr[pos] = scan.nextInt();
        }
        for (int j = 0; j < q; j++) 
        {
            System.out.println(arr[scan.nextInt()]);
        }
    }
    
    • Aquí tomamos las entradas en tal orden que la entrada se ve como si se toma en derecho girado manera.
  16. 0

    Mi solución con java

    static int[] rotLeft(int[] a, int d) {
        for (int i = 0; i < d; i++) {
            oneRotation(a);
        }
        return a;
    }
    
    static void oneRotation(int[] a) {
        int firstElement = a[0];
        for (int i = 0; i < a.length - 1; i++) {
            a[i] = a[i + 1];
        }
        a[a.length - 1] = firstElement;
    }
    
  17. 0

    Este algoritmo hace (en la mayoría) len(array)-1 swaps, y funciona tanto positiva (a la derecha) y negativo (izquierda) rotación de cantidades. La matriz es modificado en el lugar.

    No se requiere calcular el MCD, a diferencia de otros métodos similares.

    (Python 3)

    def rotate(array,amount):
        if amount<0:
            amount+=len(array)
        a=0
        b=0
        for _ in range(len(array)-1):
            b=(b+amount) % len(array)
            if b==a:
                a+=1
                b=a
            if b!=a:
                array[a],array[b] = array[b],array[a] #swap array[a],array[b]
        return array
    

    Algoritmo para girar una matriz en tiempo lineal

    Cuando un ciclo no es suficiente (si es que regresa al inicio antes de llegar a cada índice), para iniciar un nuevo ciclo, a partir de la siguiente índice.

    Nota: la rotación de los artículos a, b, c, d, … se puede hacer utilizando

    swap a,b swap a,c swap a,d

  18. -1
    public static String rotateKTimes(String str,int k){
        int n = str.length();
    
        //java substring has O(n) complexity
        return str.substring(n-k) + str.substring(0,n-k);
    }
    
    • él pidió matriz de enteros a la inversa. no string
  19. -1
    Simple Solution in O(n) time and using O(1) space:
    for e.g 1,2,3,4,5,6,7
    rotating 2 times 
    start with index 2, store a[0] as last
    Iteration 1: 1,2,1,4,3,6,5 (1-->3-->5-->7)
    Iteration 2: 1,7,1,2,3,4,5 (2-->4-->6)
    replace 1 with 6 (last value).
    
    public int[] roatateArray(int[] a,int k)
    {
        int last = a[0];
        int start = k;
        for(int j=0;j<k;j++) {
        for(int i=start;i<a.length;i+=k)
        {
            int tmp=a[i];
            a[i]=last;
            last=tmp;
        }
        start--;
        if (start<=0) break;
        }
        a[0]=last;
        return a;
    }
    

Dejar respuesta

Please enter your comment!
Please enter your name here