LC189. 轮转数组

题目描述

这是 LeetCode 上的(189. 轮转数组) ,难度为 中等

给定一个整数数组 nums,将数组中的元素向右轮转 k 个位置,其中 k 是非负数。

示例 1:

1
2
3
4
5
6
输入: 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:

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

提示:

  • 1 <= nums.length <= 105
  • -231 <= nums[i] <= 231 - 1
  • 0 <= k <= 105

进阶:

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

题解

翻转数组

本题用翻转数组的解法,1 2 3 4 5 6 7,翻转过后就会变成 7 6 5 4 3 2 1,这样后面的数字就会轮转到前面。
这时候在第k位(k = 3)分开即 7 6 5 | 4 3 2 1,将两个子数组进行翻转即5 6 7 | 1 2 3 4

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
void reverse(vector<int>& nums, int i, int j){
int t = 0;
while(i < j){
t = nums[i];
nums[i++] = nums[j];
nums[j--] = t;
}
}
void rotate(vector<int>& nums, int k) {
int len = nums.size();
k %= len;
reverse(nums, 0, len - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, len - 1);
}
};

复杂度

  • 时间复杂度:$O(n)$
  • 空间复杂度:$O(1)$

最后

我的第一想法是用击鼓传花的方式,每次指针跨越k步即nums[j+k] = nums[j]这种方式,但是在数组长度偶数轮转次数k也为偶数时,会出现奇数位置没有动的问题,记录在此,留念。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
int j = 0;
int t1 = j - k < 0 ? nums[j - k + len] : nums[j - k];
int t2 = 0;
for(int i = 0; i < len; i++){
t2 = nums[j];
nums[j] = t1;
t1 = t2;
j = j + k < len ? j + k : j + k - len;
}
}
};

image.png


LC189. 轮转数组
https://blog.daynoti.com/posts/48002/
作者
Alan White
发布于
2024年4月22日
更新于
2024年7月1日
许可协议