题目描述

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

示例一

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

示例二

输入: [-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]反转为[4,3,2,1];其次,将[5,6,7]反转为[7,6,5];之后对整个数组进行反转,得到结果[5,6,7,1,2,3,4];

我们发现归并排序的归并函数(Merge()),如果也想让空间复杂度为O(1),用的也是这种旋转方法

最后,就是处理好一些极端情况:例如数组长度为0,直接返回;如果,k大于数组长度,则右移次数为为 len % k ,即 k - len。

参考代码

class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
if(len <= 1 || k < 1 ){return;}
if (k > len) { k = k % len;}// 处理 k 大于 数组长度的情况
int i = len-k;
reverse(nums.begin(),nums.begin()+i);
reverse(nums.begin()+i,nums.end());
reverse(nums.begin(),nums.end());
}
};

谢谢访问