大家好,又见面了,我是全栈君。
Rotate Array Total Accepted: 12759 Total Submissions: 73112 My Submissions Question Solution
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
题意:循环数组,n代表数组的长度,k代表向右移动的次数。
解法一:
class Solution {
public:
void rotate(int nums[], int n, int k) {
if(n==0)return;
k=k%n;//当k大于n的时候。n次循环会回到初始位置,因此,能够省略若干次
if (k == 0) return;
int *s=new int[k];//为了一步到位的展开移动,申请k个额外空间用于保存被移出去的元素
for(int i=0;i<k;++i)
s[i]=nums[n-k+i];//保存被移出去的元素
for(int j=n-k-1;j>=0;--j)
nums[j+k]=nums[j];//移动
for(int i=0;i<k;++i)
nums[i]=s[i];//被移出的元素进行归位
free(s);
}
};
须要额外空间O(k%n)
33 / 33 test cases passed.
Status: Accepted
Runtime: 29 ms
解法二(网络获取):
三次翻转法,第一次翻转前n-k个。第二次翻转后k个,第三次翻转所有。
class Solution {
public:
void rotate(int nums[], int n, int k) {
if(n==0)return ;
k=k%n;
if(k==0)return ;
reverse(nums,n-k,n-1);
reverse(nums,0,n-k-1);
reverse(nums,0,n-1);
}
void reverse(int nums[],int i,int j)
{
for(;i<j;++i,--j)
{
int t=nums[i];
nums[i]=nums[j];
nums[j]=t;
}
}
};
33 / 33 test cases passed.
Status: Accepted
Runtime: 26 ms
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115638.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...