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

8zzbczxx  于 2021-08-20  发布在  Java
关注(0)|答案(2)|浏览(453)

我已经编写了将数组旋转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;

        }

        }
    }
}
rpppsulh

rpppsulh1#

编辑(来自上面的评论):如果我是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))。

dy2hfwbg

dy2hfwbg2#

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

相关问题