Блог

Я сделал этот код для поворота массива в k раз. В этом случае , когда я добавляю i=0, он показывает исключение «ArrayOutOfBounds», а когда я изменяю значение i на 1, он показывает неправильный вывод. Почему он показывает это исключение? И есть ли какой-нибудь способ исправить этот код?

     public void rotate(int[] nums, int k)
    { int j=0, temp=0;
        for(j=0;j<k;j  )
        {
        for(int i=0;i<nums.length;i  )
        {
              temp=nums[i-1];
              nums[i-1]=nums[i];
              nums[i]=temp;
            
        }
            
        }
    }
}

 

Правка (из комментариев выше): Если i равен 0, вы пытаетесь получить индекс -1, который вызовет исключение ArrayOutOfBounds. Если я начну с 1, то вы имеете дело не с первым номером.

Вот функция, которую вы можете использовать для поворота целых чисел вправо:

 public void rotate(int[] nums, int k) {
    int arrLen = nums.length;

    // If the number of times you want to rotate is bigger than the size of the array, get the minimum number of rotations to get the same result.
    while (k > n) {
        k = k - arrLen;
    }
    k = arrLen - k;
    k = k % arrLen;
    int i, m, n, temp;
    int g_c_d = gcd(k, arrLen);
    // Move the value in the i-th index
    for (i = 0; i < g_c_d; i  ) {
        temp = arr[i];
        m = i;
        while (true) {
            n = m   k;
            if (n >= arrLen) {
                n = n - arrLen;
            }
            if (n == i) {
                break;
            }
            arr[m] = arr[n];
            m = n;
        }
        arr[m] = temp;
    }
}

// Find the greatest common divisor of two numbers, a and b
public void gcd(int a, int b) {
    if (b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}
 

Позвольте мне вкратце объяснить, что он делает. Это один из самых известных алгоритмов: жонглирование. Вы делите массив на n наборов, где n обозначает наибольший общий делитель длины массива и количество раз, которое вы хотите повернуть. Затем вы перемещаете числа внутри наборов.

Это может быть наиболее эффективным с точки зрения времени (поскольку его временная сложность составляет O(n)).

На i=0 вы пытаетесь получить доступ nums[i-1] = num[-1] , что является недопустимой позицией, и, следовательно, возникает ArrayOutOfBound исключение.
Таким образом, измененная версия будет:

         for (j=0; j<k; j  )
        {
            for (int i=1;i<nums.length;i  )
            {
                temp=nums[i-1];
                nums[i-1]=nums[i];
                nums[i]=temp;
            } 
        }
 

Но вышеизложенное повернет массив в k разы вправо left , когда вы перемещаете элементы влево. Итак, чтобы получить right вращение, вам нужно переместить элементы с конца массива. Нравится:

         for (j=0; j<k; j  )
        {
            for (int i=nums.length-1; 0<i; i--)
            {
                // shifting towards the right
                temp=nums[i-1];
                nums[i-1]=nums[i];
                nums[i]=temp;
            } 
        }
 

Лучшим решением было бы сделать копию данного массива со значениями «0», а затем пройтись по данному массиву, чтобы получить new_index.

Формула для New_index для тактовой вращающейся матрицы:

 for(int i=0;i<nums.length;i  ){
 int new_index = (old_index k)%(a.length)
 copy[new_index] = a[old_index]
}

Now the entire function code would be:

    
public static void rotate(int[] a, int k)
    {
     int n = a.length;
     int[] copy = new int[n];
    //  fill the values with zeroes
     for(int i=0;i<n;i  ){
         copy[i]=0;
     }
    //  rotate the array
    for(int i=0;i<n;i  ){
        int new_index = (i k)%n;
        copy[new_index] = a[i];
    }
    // Now that the array is copied, copy the elements to the original array. Because they asked to rotate the given array.
    for(int i=0;i<n;i  ){
         a[i]=copy[i];
     }
    }