LeetCode 189. 旋转数组

题目描述

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

输入: [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]

思路

第一种方法

1. 将后 k 个元素存到 temp 数组里。

2. 将前 length - k 元素个向后移动，这边要注意一个细节，第 length - k 个元素先移动。

3. 将 temp 中的 k 个元素放在原来数组的前 k 个位置。

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        vector<int> temp;
        int length = nums.size();
        k = k % length;
        int m = 0;
        int i, j;
        for(j = length-k; j < length; j++)
        {
            temp.push_back(nums[j]);
        }
        int l = 0;
        for(i = length - k - 1; i >= 0;i--)
        {
            nums[length-1-l] = nums[i];
            l++;
        }
        for(i = 0; i < k; i++)
        {
            nums[i] = temp[i];
        }
    }
};

第二种方法

1. 将后 k 个元素翻转
2. 将前 length - k 个元素翻转
3. 整体翻转

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int temp;
        int length = nums.size();
        k = k % length;
        int m = 0;
        int i, j;
        int count = 0;
        for(j = length-k; j < (2 * length - k ) / 2; j++)
        {
            temp = nums[length - 1 - count];
            
            nums[length - 1 - count] = nums[j];

            nums[j] = temp;

            count++;
        }


        for(i = 0; i < (length - k) / 2; i++)
        {
            temp = nums[i];

            nums[i] = nums[length - k - 1 - i];

            nums[length - k - 1 - i] = temp;
        }

        for(i = 0; i < length / 2; i++)
        {
            temp = nums[i];

            nums[i] = nums[length - 1 - i];

            nums[length - 1 - i] = temp;
        }
    }
};