Leetcode: Rotate Array-蒲公英云

Leetcode: Rotate Array

我就是我 2022-08-05 15:21 33阅读 0赞

题目：

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.

下面使用C#语言给出示例：
方法一：

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

但是这样提交以后系统提示超时，所以采用方法二。

方法二：
先翻转数组前n-k的部分，然后翻转数组后面k个数字，然后翻转整个数组。即：
[4,3,2,1,5,6,7],
[4,3,2,1,7,6,5],
[5,6,7,1,2,3,4].

/* * 翻转数组nums中从begin到end的部分 */
private void Reverse(int[] nums, int begin, int end)
{
    int temp;
    for (int i = begin, j = end; i < j; i++, j--)
    {
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
public void Rotate(int[] nums, int k)
{
    int length = nums.Length;
    if (length <= 1)
    {
        return;
    }
    k %= length;// 处理k有肯定比length大的情况
    if (k <= 0)
    {
        return;
    }
    Reverse(nums, 0, length - k - 1);
    Reverse(nums, length - k, length - 1);
    Reverse(nums, 0, length - 1);
}