【每日一题】数组系列(5) —— 旋转数组

柔情只为你懂 2022-11-09 01:25 197阅读 0赞

> 写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我`热爱AI、热爱分享、热爱开源`！ 这博客是我对学习的一点总结与记录。如果您也对 `深度学习、机器视觉、算法、Python、C++` 感兴趣，可以关注我的动态，我们一起学习，一起进步~  
> 我的博客地址为：[【AI 菌】的博客][AI]  
> 我的Github项目地址是：[【AI 菌】的Github][AI _Github]

--------------------

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/rotate-array  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

--------------------

## 一、题目描述 ##

初步：给定一个数组，将数组中的元素向右移动 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 * 10^4
    -2^31 <= nums[i] <= 2^31 - 1
    0 <= k <= 10^5

## 二、解题思路 ##

### (1) 初步：使用中间数组 ###

主要思路：假设原来数组长度为 n，在遍历整个原数组过程中，只需将原数组下标为 i 的元素放至新数组下标为 (i+k)%n 的位置，最后将新数组拷贝至原数组即可。

C++实现如下：

class Solution { 
    public:
        void rotate(vector<int>& nums, int k) { 
            int n = nums.size();
            vector<int> temp(n); //如果已知数组长度，最好在初始化时说明长度
            for(int i=0; i<n; ++i){ 
                temp[(i+k)%n] = nums[i];
            }
            nums.assign(temp.begin(), temp.end());
        }
    };

注：assign()相当于一个拷贝函数，函数原型：void assign(const\_iterator first, const\_iterator last)，能轻松实现数组的拷贝。

测试结果：  
![在这里插入图片描述][20210314132755637.png]  
复杂度分析：

*  时间复杂度： O(n)，其中 nn 为数组的长度。
 *  空间复杂度： O(n)，使用了一个中间数组temp。

### (2) 进阶：数组反转 ###

在本题的进阶要求里，规定了O(1)的空间复杂度。所以按照第一种方法做是不满足要求的，这时我们就要思考用原地算法来解决了。

主要思路：通过观察，发现可以通过反转数组的方式巧妙地解决本题。为了更直观地表述，我们以 n=7，k=3 为例进行如下展示：

<table> 
 <thead> 
  <tr> 
   <th>操作</th> 
   <th>Value</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>原始数组</td> 
   <td>1 2 3 4 5 6 7</td> 
  </tr> 
  <tr> 
   <td>翻转所有元素</td> 
   <td>7 6 5 4 3 2 1</td> 
  </tr> 
  <tr> 
   <td>翻转 [ 0, k%( n - 1) ] 区间的元素</td> 
   <td>5 6 7 4 3 2 1</td> 
  </tr> 
  <tr> 
   <td>翻转 [ k%n, n - 1] 区间的元素</td> 
   <td>5 6 7 1 2 3 4</td> 
  </tr> 
 </tbody> 
</table>

总的来说，该方法一共分为三步：

*  先将所有元素翻转，这样尾部的 k%n 个元素就被移至数组头部
 *  然后我们再翻转 \[0, k%( n-1)\] 区间的元素，得到正确顺序的前k个数
 *  再将 \[k% n, n-1\] 区间的元素反转，得到正确顺序的后n-k个元素，即能得到最后的答案。

C++代码如下：

class Solution { 
    public:
        void reverse(vector<int>& nums, int start, int end) { 
            while (start < end) { 
                swap(nums[start], nums[end]);
                start += 1;
                end -= 1;
            }
        }
    
        void rotate(vector<int>& nums, int k) { 
            k %= nums.size();
            reverse(nums, 0, nums.size() - 1);
            reverse(nums, 0, k - 1);
            reverse(nums, k, nums.size() - 1);
        }
    };

测试结果：  
![在这里插入图片描述][20210314134836197.png]  
复杂度分析：

*  时间复杂度：O(n)，其中 n 为数组的长度。每个元素被翻转两次，一共 n 个元素，因此总时间复杂度为 O(2n)=O(n)。
 *  空间复杂度：O(1)，没有使用额外的数组。

--------------------

***由于水平有限，博客中难免会有一些错误，有纰漏之处恳请各位大佬不吝赐教！***

![在这里插入图片描述][2020090613542669.png_pic_center]  
***推荐文章***

*  [【C++21天养成计划】不聊学习只谈干货（Day1）][C_21_Day1]
 *  [【人生苦短，我学 Python】序言——不学点Python你就out了？][Python_Python_out]
 *  [TF2.0深度学习实战（一）：分类问题之手写数字识别][TF2.0]

[AI]: https://blog.csdn.net/wjinjie
[AI _Github]: https://github.com/Keyird/DeepLearning-TensorFlow2.0
[20210314132755637.png]: /images/20221023/9623d76337e74fc3baff5f254d6b18c5.png
[20210314134836197.png]: /images/20221023/c69fa18961d845c9aeba3809c0eb6f0a.png
[2020090613542669.png_pic_center]: /images/20221023/4eb4c68c7d244c5f89a6195a1b6aadaf.png
[C_21_Day1]: https://blog.csdn.net/wjinjie/article/details/105316043
[Python_Python_out]: https://ai-wx.blog.csdn.net/article/details/110674503
[TF2.0]: https://ai-wx.blog.csdn.net/article/details/104700834