189 Rotate Array

Rotate an array ofnelements to the right byksteps.

For example, withn= 7 andk= 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.

Solution 1 (Extra Space, O(n)): Hash to the location in the array the corresponds with its its rotated position.

void rotate(vector<int>& nums, int k) 
{
    vector<int> r_nums(nums.size());

    for (int i = 0; i < nums.size(); i++) {
        int rotate_hash = (i + k) % nums.size();
        r_nums[rotate_hash] = nums[i];
    }
    nums = r_nums;
}

int main()
{
    vector<int> nums = { 1,2,3,4,5,6,7 };
    rotate(nums, 3);

    print(nums);
}

Solution 2 (Constant Space, O(n)): Reverse the array entirely, and the reverse two segments divided at k.

Example:

Input
nums: 1 2 3 4 5 6 7
k   : 3

rev :         7 6 5 4 3 2 1
rev(0, k) :   5 6 7 4 3 2 1
rev(k, end) : 5 6 7 1 2 3 4

void rotate(vector<int>& nums, int k)
{
    k = k % nums.size();

    reverse(nums.begin(), nums.end());
    reverse(nums.begin(), nums.begin() + k);
    reverse(nums.begin() + k, nums.end());
}

int main()
{
    vector<int> nums = { 1,2,3,4,5,6,7 };
    rotate(nums, 3);
    print(nums);
}