题目大意：
旋转数组
给定一个数组，将数组中的元素向右移动 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) 的 原地 算法。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=189
解题思路分析：
解法一：辅助数组
我们利用原数组copy一份新数组，然后将copy[i]的元素赋值到nums[i+k]即可。注意下标i+k可能越界，因此我们需要求它与数组长度的余数。
实现代码：
public void rotate(int[] nums, int k) {
int[] copy=Arrays.copyOf(nums,nums.length);
for(int i=0;i<nums.length;i++){
int index=(i+k)%nums.length;
nums[index]=copy[i];
}
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Array.
Memory Usage: 41.9 MB, less than 5.77% of Java online submissions for Rotate Array.
解法二：原地算法
题目要求使用常数级变量空间的原地算法，这就意味着不能使用辅助数组。我们先看一个例子：
nums[]={1,2,3,4,5,6,7}; n=3;通过肉眼，我们很容易发现，变化前后数组的特性：
{1, 2, 3, 4, 5, 6, 7}
{5, 6, 7, 1, 2, 3, 4}
实际上我们就是将红蓝两部分的位置颠倒了一下而已，这实际上是二次翻转算法，我们先将红色部分数字进行翻转，再对蓝色部分数字进行翻转，最后再将整个数组翻转即可。
1 2 3 4 5 6 7 // 原数组
4 3 2 1 5 6 7 // 翻转前部
4 3 2 1 7 6 5 // 翻转后部
5 6 7 1 2 3 4 // 整体翻转
实现代码：
public void rotate(int[] nums, int k) {
k=k%nums.length;
// 翻转前半部分
int l=0,r=nums.length-k-1;
reverse(nums,l,r);
// 翻转后半部分
l=nums.length-k;
r=nums.length-1;
reverse(nums,l,r);
// 整体翻转
l=0;
r=nums.length-1;
reverse(nums,l,r);
}
void reverse(int[] nums, int l, int r){
// 由外至内两两数字交换位置
while(l<r){
nums[l]=nums[l]^nums[r];
nums[r]=nums[l]^nums[r];
nums[l]=nums[l]^nums[r];
l++;
r--;
}
}本解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Rotate Array.
Memory Usage: 42 MB, less than 5.77% of Java online submissions for Rotate Array.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-189-rotate-array-解题思路分析/