Fork me on GitHub

Leetcode-初级算法-数组循环右移

本文首发于我的个人Blog阿西BUG,欢迎大家批评指正

题目

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

自己的思路

在数组元素个数 n 不为0的前提下,分3种情况
1.如果 k 和 n 相同,则数组不变
2.如果 k 小于 n ,则对数组进行 k 次循环,把最后一个元素移到第一个元素,其他依次后移
3.如果 k 大于 n ,则对数组进行 k-n 次循环,重复步骤2

耗时: 384ms

这个思路大概是最笨的方法,不得不承认,自己对于算法还是弱鸡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
void rotate(vector<int>& nums, int k) {
if (nums.empty())
return;

if (nums.size() > k){
for (int j = 0; j < k; j++){
int temp = nums[nums.size() - 1];
for (int i = nums.size() - 1; i > 0; i--){
nums[i] = nums[i - 1];
}
nums[0] = temp;
}
}
else if (nums.size() < k){
rotate(nums, k-nums.size());
}

for (int i = 0; i < nums.size(); i++){
cout << nums[i];
}
}
};

网上的优秀思路

这个思路是使用了C++标准库函数 reverse
假设输入数组的下标是0 ~ n-1,需要旋转的步数是k,那么按照下面的方法就可以完成旋转数组
(其中reverse表示用双指针交换的方法翻转数组):
step 1. reverse原来的数组。
step 2. reverse 0~ k-1。
step 3. reverse k ~ n-1。
那么得到的新数组就是个旋转数组了。

举个例子来说是这样的:
元素组: 1 2 3 4 5 翻转步长:k=3
step 1 reverse原来的数组: 5 4 3 2 1
step 2 reverse 0~ k-1: 3 4 5 2 1
step 3 reverse k ~ n-1: 3 4 5 1 2
最后的【3 4 5 1 2】就是旋转数组的结果了,这种方法的时间复杂度是o(n),空间复杂度是o(1),是非常好的方法了
耗时: 12ms

1
2
3
4
5
6
7
8
9
class Solution {
public:
void rotate(vector<int>& nums, int k) {
k = k % nums.size();
reverse(nums.begin(), nums.begin() + nums.size() - k);
reverse(nums.begin() + nums.size() - k, nums.end());
reverse(nums.begin(), nums.end());
}
};

本文标题:Leetcode-初级算法-数组循环右移

文章作者:阿西BUG

发布时间:2018年09月13日 - 22:09

最后更新:2018年09月13日 - 22:09

原始链接:http://blog.92yu.win/2018/09/13/Leetcode-初级算法-数组循环右移/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

阿西BUG wechat
福利干货铺(YM-TALK)-- 互联网福利干货大集合
Enjoy it ? Donate for it ! 欣赏此文?求鼓励,求支持!
>