算法练习——旋转数组

2021年1月8日LeetCode每日一题为189. 旋转数组,如果按照题目下方的说明,不使用额外空间的原地算法,写起来可能比较费劲,最简单的就是使用一个双层循环,一个个元素往后搬,或者拿一个数组,从旋转后将会在第一位元素开始,直至填满新数组,然后将这个数组元素再对应回原来的数组中,这里为了防止做多余操作,先将k对数组长度进行取余。代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int[] newArr = new int[nums.length];
int end = nums.length - k, p = end, count = 0;
while (count != nums.length) {
newArr[count++] = nums[p % nums.length];
p++;
}
for(int i = 0; i < nums.length; i++) {
nums[i] = newArr[i];
}
}
}

然后尝试了第二种方法,比较暴力,直接将最后一个不断往前挪到第一位,挪k次。很不幸的是超出了时间限制,也是在预料之中。代码如下:

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

这里附上官方题解,上面这种暴力位移的方法可以学习题解中的环状替换方法,使用到了gcd来减少循环的次数。

今天的题目相对简单,但是限定在时间复杂度为O(n),空间复杂度为O(1)的情况下,就需要用一些技巧,比如题解最后一种翻转数组的方法,非常巧妙的原地翻滚,达到不断替换的效果。