LeetCode 189. Rotate Array

题目

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

解析

题目是很好理解的，即是将数组旋转k步，达到目标数组。但是题目中说至少有3种方法，因此，在此提供3种思路。

1. 最容易想到的一种方法是，旋转3步，即为平移三步，从数组末尾向前，每次循环平移一步，要保存最后一个元素的value，每步循环结束后将保存的value赋值给nums[0]；

2. 第二种方法是以空间换时间。malloc一个和原数组长度相同的新数组newNums，先将原数组保存至newNums，然后再循环新数组计算位置并赋值回去，nums[(i + k) % numsSize] = newNums[i];，注意需要取余；
   也可以采用部分赋值的方法，即从numsSize-k位置平分为两半，后面部分赋到新数组前面部分，前面部分赋到新数组后面部分。最后再memcpy新数组->原数组。这样做也可以。

3. 第三种方法是交换，如下演示。

1,2,3,4,5,6,7,8
k = 4
最终结果为5,6,7,8,1,2,3,4
（1）交换0 -> 3（3 = 8 - 4 -1，即前半部分），结果为
4,3,2,1,5,6,7,8
（2）交换4->7（后半部分），结果为
4,3,2,1,8,7,6,5
整体交换
5,6,7,8,1,2,3,4 -->最终结果

此处的交换为两个value之间的交换。

误区：级联计算位置并且赋值的方法是不对的，反例为1,2,3,4,5,6，k=2，使用级联计算位置会发现：
(0 + 2) % 6 = 2
(2 + 2) % 6 = 4
(4 + 2) % 6 = 0
回到0了，只计算了3个位置。因此这样做是不正确的。

代码（C语言）

// 方法1：平衡k步
void rotate(int* nums, int numsSize, int k) {
    if (nums == NULL || numsSize == 0 || k == 0 || (k % numsSize == 0))
        return ;
    
    k = k % numsSize;
    
    int firstNum = 0;
    
    for (int i = 0; i < k; ++i) {
        firstNum = nums[numsSize - 1];
        
        for (int j = numsSize - 2; j >= 0; --j) {
            nums[j + 1] = nums[j];
        }
        
        nums[0] = firstNum;
    }
}

// 方法2：空间换时间
void rotate2(int* nums, int numsSize, int k) {
    if (nums == NULL || numsSize == 0 || k == 0 || (k % numsSize == 0))
        return ;
    
    k = k % numsSize;
    
    int* newNums = (int*)malloc(sizeof(int) * numsSize);
    
    // store all nums to newNums array
    for (int i = 0; i < numsSize; ++i) {
        newNums[i] = nums[i];
    }
    
    // get new position and store back
    for (int i = 0; i < numsSize; ++i) {
        nums[(i + k) % numsSize] = newNums[i];
    }
    
    free(newNums);
}

// 方法3：循环交换
void reverseRotate(int* front, int* rear);
void rotate3(int* nums, int numsSize, int k) {
    if (nums == NULL || numsSize == 0 || k == 0 || (k % numsSize == 0))
        return ;
    
    k = k % numsSize;
    
    reverseRotate(&nums[0], &nums[numsSize - k - 1]);
    reverseRotate(&nums[numsSize - k], &nums[numsSize - 1]);
    reverseRotate(&nums[0], &nums[numsSize - 1]);
}

void reverseRotate(int* front, int* rear) {
    if (front == NULL || rear == NULL)
        return ;
    
    while (front < rear) {
        int tempInt = (*front);
        
        (*front) = (*rear);
        (*rear) = tempInt;
        
        ++front;
        --rear;
    }
}