LeetCode初级-旋转数组

题目：

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

题目分析：

说实话，找规律找到的。下面举个栗子：

[1,2,3,4,5,6,7] ， k = 3
原始：

1	2	3	4	分割	5	6	7

把 k 位置之前的数组看成一组，进行反转。（第一个for循环）

4	3	2	1	分割	5	6	7

把 k 位置之后的数组也看成一组，反转。（第二个for循环）

4	3	2	1	分割	7	6	5

最后把整个数组反转。（第三个for循环）

5	6	7	1	2	3	4

注：t1 和 t2 用来标记反转时下标位置，tr 用作交换时的中间量。

C++代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k =  k % nums.size();
        
        int t1 = 0, t2 = 0;
        int tr;
        for (t1 = 0, t2 = nums.size() - k - 1; t1 <= t2;++t1, --t2){
            tr = nums[t1];
            nums[t1] = nums[t2];
            nums[t2] = tr;
        }
        
        for (t1 = nums.size() - k, t2 = nums.size() - 1; t1 <= t2;++t1, --t2){
            tr = nums[t1];
            nums[t1] = nums[t2];
            nums[t2] = tr;
        }
        
        for (t1 = 0, t2 = nums.size() - 1; t1 <= t2;++t1, --t2){
            tr = nums[t1];
            nums[t1] = nums[t2];
            nums[t2] = tr;
        }
    }
};

使用STL会比较耗时，可能是要加载STL库的原因吧，今天才发现。