将给定数组的元素向右旋转 k 次

Question

我已经编写了这段代码来将数组旋转 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;
            
        }
            
        }
    }
}

Answer 1

在 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;
            } 
        }

Answer 2

编辑（来自上面的评论）：如果 i 为 0，您正在尝试获取 -1 的索引，这将引发 ArrayOutOfBounds 异常。如果 i 从 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)）。

Answer 3

更好的解决方案是使用值“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];
     }
    }

将给定数组的元素向右旋转 k 次

rotate the elements of the given array k times to the right

java

arrays

for-loop

exception