题:给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
1.示例 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.算法思路:
一般人拿到这道题大概会使用一个中间值来一点一点一次一次的旋转,但是 这道题我却用了一个不一样的思路:先将两个由旋转长度分开的部分各自颠倒,再将整个字符串颠倒则可得到旋转后的字符串;
3.代码实现:
void rotate(int* nums, int numsSize, int k)
{
int i, z;
k = fabs(k % numsSize);//转过一周就等于没转,因此对其求余
for (i = 0; i < fabs((numsSize - k) / 2); i++)//fabs为字符串长度小于旋转长度
{
z = nums[i];
nums[i] = nums[numsSize - k - 1 - i];
nums[numsSize - k - 1 - i] = z;
}
for (i = 0;i<fabs(k/2); i++)
{
z = nums[numsSize - k + i];
nums[numsSize - k + i] = nums[numsSize - 1 - i];
nums[numsSize - 1 - i] = z;
}
for (i = 0; i < fabs(numsSize / 2); i++)
{
z = nums[i];
nums[i] = nums[numsSize - 1 - i];
nums[numsSize - 1 - i] = z;
}
}