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

写在前面：大家好！我是【AI 菌】，一枚爱弹吉他的程序员。我热爱AI、热爱分享、热爱开源！ 这博客是我对学习的一点总结与记录。如果您也对 深度学习、机器视觉、算法、Python、C++ 感兴趣，可以关注我的动态，我们一起学习，一起进步~
我的博客地址为：【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
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
 

二、解题思路

(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()); }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
 

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

测试结果：

复杂度分析：

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

(2) 进阶：数组反转

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

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

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

• 先将所有元素翻转，这样尾部的 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); }
};

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
 

测试结果：

复杂度分析：

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

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

推荐文章

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

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/114784124