原题地址
https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/23/
题目描述
给定一个数组,将数组中的元素向右移动 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) 的原地算法。
1. 暴力解法
在刚看到这个题目时,脑子里第一时间想到的,最简单的解法:创建一个temp
数组整个把原数组复制过来,然后再按照旋转后的结果逐个元素地覆盖原数组。代码如下:
void
rotate(int* nums, int numsSize, int k)
{
int i, j;
int temp[numsSize];
/* 复制数组元素 */
for (i = 0; i < numsSize; i++)
temp[i] = nums[i];
/* 把后k个元素覆盖到原数组的前k个位置上 */
j = 0;
for (i = numsSize - k; i < numsSize; i++, j++)
nums[j] = temp[i];
/* 剩余部分按顺序覆盖 */
for (i = 0; i < numsSize - k; i++, j++)
nums[j] = temp[i];
}
时间复杂度,复制数组为n
,覆盖原数组也是n
,所以总的时间复杂度为
O
(
n
)
O (n)
O(n)。
空间复杂度,因为有temp
数组的存在,所以需要n
个元素的空间,因此空间复杂度也是
O
(
n
)
O(n)
O(n)。
2. 递归算法
由于暴力算法并不满足问题对空间复杂度的要求,因此琢磨了一下其他的解法。在手动旋转的过程中发现了一个不需要额外空间的算法:
- 将前
k
个数据与数组最后k
个数据逐个交换
- 将后
n - i * k
个数据视为新的数组,重复操作1,注意k
要对剩余元素数量n - i * k
取模,以保证数组的访问不会越界,其中i
表示操作1执行的次数
- 当
k = 0
或者只剩一个数据时,算法结束。
举个栗子,对于数组[1, 2, 3, 4, 5]
,n = 5, k = 2
,那么每一轮的操作结果如下所示:
- 将前2个与后2个数据交换:
[1, 2, 3, 4, 5] → [4, 2, 3, 1, 5] → [4, 5, 3, 1, 2]
- 将
[3, 1, 2]
视为新数组,k
对3取模还是2,交换前2个数据与后2个数据:[4, 5, 3, 1, 2] → [4, 5, 1, 3, 2] → [4, 5, 1, 2, 3]
- 将
[2]
视为新数组,由于只剩一个数据,算法结束
这个算法的思想十分适合递归,因此直接一波递归。代码如下所示:
/* begin表示新数组开始的下标 */
void
rotate(int *nums, int begin, int numsSize, int k)
{
/* 到最后几轮,k很有可能会比剩余的数组数量长 */
k = k % (numsSize - begin);
if (k == 0)
return;
if (begin >= numsSize - 1)
return;
int i, j;
/* 逐个交换 */
for (i = begin, j = 0; i < numsSize && j < k; i++, j++)
{
int temp = nums[i];
nums[i] = nums[numsSize - k + j];
nums[numsSize - k + j] = temp;
}
/* 递归调用处理 */
return rotate_r(nums, begin + k, numsSize, k);
}
void
rotate(int *nums, int numsSize, int k)
{
rotate_r(nums, 0, numsSize, k);
}
此外,递归操作会占用大量的栈空间,虽然这个代码用了尾递归,但还是不如循环。所以可以改成循环来处理,比较简单,不再列出代码。
3. 更简单的算法
当我把代码提交上去后,发现还有代码时间比我的算法还要快,于是看了一下。代码如下:
void reverse(int* nums,int left,int right){
while(left<right){
int temp=nums[left];
nums[left++]=nums[right];
nums[right--]=temp;
}
}
void rotate_alg1(int* nums, int numsSize, int k){
k%=numsSize;//若k>numsSize则移动位置为余数;
/* 先整个倒序 */
reverse(nums,0,numsSize-1);
/* 前k个倒序 */
reverse(nums,0,k-1);
/* 后n-k个倒序 */
reverse(nums,k,numsSize-1);
}
理解起来更加简单了
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)