Leetcode189

LeetCode189：旋转数组         给定一个数组，将数组中的元素向右移动 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) 的 原地 算法。

解法一：基于旋转一次的for循环方法 (超出时间限制)

/*********************************
基于旋转一次的for循环方法 (超出时间限制)
思路：先完成旋转一次时的基本函数，
然后再for循环K次。
*****************************/
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        for (int j = 0; j<k; j++)
            rotate1(nums);
    }
    void rotate1(vector<int>& nums1) {
        int Size1 = nums1.size();
        int temp = nums1[Size1 - 1];
        for (int i = Size1 - 1; i>0; i--)
        {
            nums1[i] = nums1[i - 1];
        }
        nums1[0] = temp;
    }
};

解法二：老实的一步步移动 (超出时间限制)

/*********************************
基于旋转一次的for循环方法 (超出时间限制)
思路：先完成旋转一次时的基本函数，
然后再for循环K次。
*****************************/
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (k >= nums.size())
            k %= nums.size();
        if (k != 0)
        {
            while (k)
            {
                int temp = nums[nums.size() - 1];
                for (int i = nums.size() - 2; i >= 0; i--)
                {
                    nums[i + 1] = nums[i];
                }
                nums[0] = temp;
                k--;
            }
        }
    }
};

解法三：用一个数组保留后k位数组，将前面得数组向后移动k位，再写入前面得数组(执行用时12ms,内存消耗9.9MB)

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        if (k >= nums.size())
            k %= nums.size();
        if (k != 0)
        {
            vector<int> a(k);
            int idx = 0;
            for (int i = nums.size() - k; i<nums.size(); i++)//保留后k位数据
            {
                a[idx] = nums[i];
                idx++;
            }
            idx = 0;
            for (int i = nums.size() - k - 1; i >= 0; i--)//将前面数据移动k位
            {
                nums[nums.size() - 1 - idx] = nums[i];
                idx++;
            }
            for (int i = 0; i<k; i++)//将后k位数据写入
            {
                nums[i] = a[i];
            }
        }
    }
};

main()函数

#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;

int main()
{
    vector<int> num;
    cout << "请输入数组的大小 Size: " << endl;
    int Size;
    cin >> Size;
    cout << "请输入数组的元素： " << endl;
    int Currval;
    for (int i = 0; i < Size; i++)
    {
        cin >> Currval;
        num.push_back(Currval);
    }
    Solution answer;
    int K;
    cout << "请输入旋转次数K：" << endl;
    cin >> K;
    answer.rotate(num, K);
    cout << "旋转K次后新数组为： " << endl;
    vector<int>::iterator it;
    for (it = num.begin(); it != num.end(); it++)
        cout << *it<<" ";

    system("pause");
    return 0;
}