Advantrue 1 - Leetcode 189 - Rotate Array

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

  1. https://leetcode-cn.com/problems/rotate-array/(中文)
  2. https://leetcode.com/problems/rotate-array/(en)

示例 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) 的原地算法。

解题思路

首先考虑考虑brute-force暴力解法,要使数组中的元素整体右移k位,最直接的方式是循环k次,每次循环让每个元素依次跟最后一个元素进行交换swap即可。

例如: input : [1, 2, 3, 4], k = 1
loop1: 4, 2, 3, 1 ->
4, 1, 3, 2 ->
4, 1, 2, 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length <= 1) return;

for (int i = 0; i < k; i++) {
int last = nums[nums.length-1];
for (int j = 0; j < nums.length; j++) {
int temp = nums[j];
nums[j] = last;
last = temp;
}
}
}
}

复杂度分析(Compelxity Analysis):

  • 时间复杂度(Time complexity): $O(kn)$
  • 空间复杂度(Space complexity): $O(1)$

Submission status:

该解法通过所有测试用例,但是执行时间为109 ms, 击败14.9%java代码提交。

解题思路二:

利用辅助数组,先将需要移动变换的元素放在移动后的位置,再将辅助数组元素移回原数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length < 2) return;

int[] aux = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
aux[(i+k) % nums.length] = nums[i];
}

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

复杂度分析(Compelxity Analysis):

  • 时间复杂度(Time complexity): $O(n)$
  • 空间复杂度(Space complexity): $O(n)$

Submission status:

代码提交运行时间: 1 ms 击败53.8%java提交代码。

解题思路三:

除了上面给出的第二种方案,还有更好的解题方法,能够做到O(n)运行时间,以及O(1)的空间复杂度.

思路: 拿题目给定的例子来说,[1,2,3,4,5,6,7], k = 3.
首先将数组划分成两个部分: 0~nums.length-k-1,即[1,2,3,4]和nums.length-k ~ nums.length-1],即[5,6,7],把两个部分进行翻转,此时数组变成[4,3,2,1,7,6,5].
最后,将整个数组进行翻转即可得到我们想要的结果: [5,6,7,1,2,3,4].

需要注意的是,需要对k进行处理,当k > nums.length情况,会出现越界情况。
解决方法: 使k进行 mod nums.length运算(k = k % nums.length).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public void rotate(int[] nums, int k) {
if (nums == null || nums.length < 2) return;

k %= nums.length;
reverse(nums, 0, nums.length-k - 1);
reverse(nums, nums.length-k, nums.length-1);
reverse(nums, 0, nums.length-1);
}
private void reverse(int[] nums, int i, int j) {
while (i < j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
i++;
j--;
}
}
}

复杂度分析(Complexity Analysis):

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

Submission status:

代码提交运行时间: 0 ms, 击败100%java提交代码。

总结

在处理数组问题时,需要非常小心,时刻注意边界,避免发生数组越界问题。

-------------The End Thanks for reading.-------------
Donate me, thanks for your support!