[Leetcode 189]Rotate Array

Description:

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

Example 1:

Input: nums = [1,2,3,4,5,6,7], 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: nums = [-1,-100,3,99], 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]

Constraints:

• 1 <= nums.length <= 105
• -231 <= nums[i] <= 231 - 1
• 0 <= k <= 105

C code solution 1:

void rotate(int* nums, int numsSize, int k){
    //let k rotate less than one full round
    k %= numsSize;
    int *tmp = (int*)calloc(k, sizeof(int));
    //place the evicted element to tmp
    for(int i=0; i<k; i++){
        tmp[i] = nums[numsSize-k+i];
    }
    //the original elements move k steps to right 
    for(int i=0; i<numsSize-k; i++){
        nums[numsSize-1-i] = nums[numsSize-1-k-i];
    }
    //place the evicted elements back to the left
    for(int i=0; i<k; i++){
        nums[i] = tmp[i];
    }
}

Explanation:

先將最後k個elements放入tmp，再將nums剩下的elements向右移動k步，最後將tmp所有的elements加在nums的前方。

C code solution 2:

void reverse(int* nums, int lo, int hi){
    while(lo < hi){
        //swap
        nums[lo] = nums[lo] + nums[hi];
        nums[hi] = nums[lo] - nums[hi];
        nums[lo] = nums[lo] - nums[hi];
        //move pointer
        lo++;
        hi--;
    }
}
void rotate(int* nums, int numsSize, int k){
    //let k rotate less than one full round
    k %= numsSize;
    reverse(nums, 0, numsSize-1-k);
    reverse(nums, numsSize-k, numsSize-1);
    reverse(nums, 0, numsSize-1);
}

Explanation:

用心體會!!
k個準備要移到前面的elements，要保持順序，而剩餘的也是要保持順序。若用swap element的方式會希望兩個subarray各自先reverse，最後的reverse才會正確。

1234 567
-> 1234 765
-> 4321 765
then, swap the first and the last, the second and the secondly last...
-> 567 1234