问题描述
给定一个数组和一个非负整数 k，要求将数组末尾 k 个数字进行翻转到数组前面来。题目链接：**点我**
样例输入输出
输入：nums = [1,2,3,4,5,6,7], k = 3
输出：[5,6,7,1,2,3,4]
解释：第一次旋转后数组为：[7,1,2,3,4,5,6]
第二次旋转后数组为：[6,7,1,2,3,4,5]
第三次旋转后数组为：[5,6,7,1,2,3,4]
输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释：第一次旋转后数组为：[99,-1,-100,3]
第二次旋转后数组为：[3,99,-1,-100]
问题解法
解法一
暴力解法，按照题意，一次挪动一个元素。此解法时间复杂度为 O(nk)，空间复杂度为 O(1)。代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution
{
public void rotate(int[] nums, int k)
{
if (nums == null || nums.length <= 1 || k % nums.length == 0)
{
return;
}
int n = k % nums.length;
for (int i = 1; i <= n; i++)
{
int temp = nums[nums.length - 1];
System.arraycopy(nums, 0, nums, 1, nums.length - 1);
nums[0] = temp;
}
}
}
|
解法二
利用额外空间存储变化的元素，将旋转的元素列表存储到临时数组中，然后将数组剩余的元素挪到目标位置，最后将临时数组的元素放入原先数组中。此种解法时间复杂度为 O(n)，空间复杂度为 O(k)，代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution
{
public void rotate(int[] nums, int k)
{
if (nums == null || nums.length <= 1 || k % nums.length == 0)
{
return;
}
int n = k % nums.length;
int[] temp = Arrays.copyOfRange(nums, nums.length - n, nums.length);
System.arraycopy(nums, 0, nums, n, nums.length - n);
System.arraycopy(temp, 0, nums, 0, n);
}
}
|
解法三
利用数组翻转的特性，先将数组全部倒序，然后对前 k 个元素进行倒序，再对数组后部分 nums.length - k 个元素进行倒序。此种解法的时间复杂度为 O(n)，空间复杂度为 O(1)。此做法参考：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
代码如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution
{
public void rotate(int[] nums, int k)
{
if (nums == null || nums.length <= 1 || k % nums.length == 0)
{
return;
}
int n = k % nums.length;
reverse(nums, 0, nums.length - 1);
reverse(nums, 0, n - 1);
reverse(nums, n, nums.length - 1);
}
private void reverse(int[] nums, int start, int end)
{
while (start < end)
{
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
}
|
参考资料
https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/