Leetcode: Rotate Array
Leetcode: Rotate Array
卡尔曼和玻尔兹曼谁曼
发布于 2019-01-25 14:43:33
发布于 2019-01-25 14:43:33
题目：
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.
下面使用C#语言给出示例： 方法一：
public void Rotate(int[] nums, int k)
{
int temp;
int length = nums.Length;
for (int i = 0; i < k; i++)
{
temp = nums[length - 1];
for (int j = length - 1; j > 0; j--)
{
nums[j] = nums[j - 1];
}
nums[0] = temp;
}
}但是这样提交以后系统提示超时，所以采用方法二。
方法二： 先翻转数组前n-k的部分，然后翻转数组后面k个数字，然后翻转整个数组。即： [4,3,2,1,5,6,7], [4,3,2,1,7,6,5], [5,6,7,1,2,3,4].
/*
* 翻转数组nums中从begin到end的部分
*/
private void Reverse(int[] nums, int begin, int end)
{
int temp;
for (int i = begin, j = end; i < j; i++, j--)
{
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
public void Rotate(int[] nums, int k)
{
int length = nums.Length;
if (length <= 1)
{
return;
}
k %= length;// 处理k有肯定比length大的情况
if (k <= 0)
{
return;
}
Reverse(nums, 0, length - k - 1);
Reverse(nums, length - k, length - 1);
Reverse(nums, 0, length - 1);
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2015年03月04日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读