189. 旋转数组

难度：简单

题目

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1：

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2：

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明：

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为\(O(1)\)的原地算法。

Reference

题解

基本思路： 先反转整个数组，再以第\(k\)个元素为界，分别反转\(k\)之前的部分与\(k\)及\(k\)之后的部分即可。

代码如下：

void Reverse(int* nums, int numsSize)
{
    int head = 0, tail = numsSize - 1, temp = 0;
    while(tail > head)
    {
        temp = nums[head];
        nums[head] = nums[tail];
        nums[tail] = temp;
        tail--;
        head++;
    }
}
void rotate(int* nums, int numsSize, int k){
    if (numsSize < 2)
        return;
    k %= numsSize;
    Reverse(nums, numsSize);
    Reverse(nums, k);
    Reverse(nums + k, numsSize - k);
}

评论