leetcode 总结 05 旋转数组

发表于 更新于 分类于

leetcode 05 旋转数组

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

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

示例 1:

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

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

作者：力扣 (LeetCode)
链接：https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/x2skh7/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//解题思路：在没有看清要求的时候就在考虑，取出最后一节，然后逐个拼接在最前面的， 但是 o(1)的限制貌似不太好
//思路二 ， 最后几位逆序，然后逐个插入在数组最前面 ， （方法可行，但是每次插入一个数子，整个数组移动，不合适）
// 非常要注意一点 ， K 是移动的次数， 不是第几位 
// 先分模块儿 ， 再分
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int numLen = nums.size(); // 获取nums 的长度
        if(k > numLen) // 如果超过数组本身长度
        {
            k = k % numLen; // 超过本身的就没必要去旋转
        }
      	// [1,2,3,4,5,6,7] 3 
      	// A [1,2,3,4]   B [5,6,7]
      	// 分为 A   B  两节 ，  第一节 ， 从 0 开始 到 numLen - 1 - k 长度结
        myRotate(nums, 0, numLen - 1 - k); // 处理以后是 [4,3,2,1]
        myRotate(nums, numLen - k, nums.size() - 1); // 第二节 从 上面长度结尾 后面的一位开始 ， 到整个数组的结尾 处理以后是 [7,6,5]
        myRotate(nums,0,nums.size() - 1); // 原本 [4,3,2,1,7,6,5]  整个翻转之后就变成了 [5,6,7,1,2,3,4]  符合需求
    }
    void myRotate(vector<int>& nums, int start, int end)  // 使用双指针 ，头结点和尾节点，然后两者之间交换
    {
        while(start < end)
        {
            int tmp  = nums[start];
            nums[start] = nums[end];
            nums[end] = tmp;
            start ++;
            end --;
        }
    }
};