**
Question:
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.
**
My code:
public class Solution {
public void rotate(int[] nums, int k) {
k = k % nums.length;
int sentinel = nums.length - k;
int[] temp = new int[nums.length];
for (int i = 0; i < nums.length; i++)
if (i < sentinel)
temp[i + k] = nums[i];
else
temp[i + k - nums.length] = nums[i];
for (int i = 0; i < nums.length; i++)
nums[i] = temp[i];
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = {1,2};
for (int i = 0; i < nums.length; i++)
System.out.print(nums[i] + " ");
System.out.println();
test.rotate(nums, 1);
for (int i = 0; i < nums.length; i++)
System.out.print(nums[i] + " ");
}
}
My test result:
这次的还是比较简单。。。说下思路吧。
首先这个k得理解好。是用来移动的步数。如果移动的范围超出了右边的limit，那么就接着从左边开始移动。很类似于图像处理时算的neighbour。也需要进行这样的映射。
那么一定存在这么一个点，他的左边全部是可以正常移动相应的k，而这个点已经这个点的右边，移动k步后都会转到左边。
所以必须找到这个点，我设为，sentinel.
找到了之后，就进行判断被，小于他的正常移动。大于等于他的，正常移动后再减去一个数组长度就到左边去了。
但是这次作业有两个问题需要注意。
1.k是可以任意大的，也就是说可以大于数组长度。因为可以任意移动步数。所以，必须首先对k进行处理。 k = k % nums.length;
2.我们要明白这个方法是干什么的。我们传进来一个数组的引用，然后处理，再返回。
一开始，处理完后，我直接
nums = temp;
以为这样就可以直接指向这个处理好的数组了。的确也是如此。
**
但是，这是错的。
仔细回想下C语言里面学的函数调用时栈的结构。Java类似。
我们在main函数中传入nums时，会拷贝一份指向nums的引用，存放在方法rotate的活动空间上。所以，如果传入的直接就是数（int,double,float...），我们在活动区间修改这些传入参数是不会影响到原数据的。这就是所谓的改变形参不会改变实参。
但是这里不同，传入的是地址，或者说，指向数组的一个指针。
所以我们可以通过修改这个指针指向的内容，而达到修改实参的效果。
但是，我又犯了一个错误。我以为nums = temp；就可以修改实参了。
其实是大错特错的。
因为在那块内存位置处，我拷贝的是指向实参nums的地址。现在我把该地址抹掉，存入指向temp的地址。那么，原nums的数据发生改变了吗？
没有。因为我们在方法rotate中进行的操作没有返回到实参中。
所以，必须得将temp数组再重新拷贝给nums
**
这道题，我多设了一个数组来进行处理。这是上普林斯顿算法课时，老师在讲 merge sort时给我的灵感。所以说，那些课的东西还是有用的。
**
总结下：
1.k要注意可以随意大小
2.在方法中，如何修改实参的内容
之前学习的C语言，对于了解Java还是很有用的。正如我现在学习Java，了解OOP，然后学校的C++考试我其实就没有那么虚了。
**
发现LJ有种让人欲罢不能的感觉。也许也是因为实在不想学习电气的缘故吧。。。
Anyway,
Good luck, Richardo!
重做了下，看了答案知道了如何使用
time O(n), Space: O(n) 的做法。
public class Solution {
/* Solution 1: time: O(n) space: O(n)
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0)
return;
int n = nums.length;
int[] ret = new int[n];
k = k % n;
for (int i = k; i < n; i++)
ret[i] = nums[i - k];
for (int i = 0; i < k; i++)
ret[i] = nums[i + n - k];
for (int i = 0; i < n; i++)
nums[i] = ret[i];
}
*/
/** Solution 2: time O(n), Space: O(1) */
public void rotate(int[] nums, int k) {
if (nums == null || nums.length == 0)
return;
int n = nums.length;
k = k % n;
reverse(0, n - k, nums);
reverse(n - k, k, nums);
reverse(0, n, nums);
}
private void reverse(int begin, int length, int[] nums) {
for (int i = begin; i < begin + length / 2; i++) {
int temp = nums[i];
int swapIndex = begin + length - 1 - (i - begin);
nums[i] = nums[swapIndex];
nums[swapIndex] = temp;
}
}
public static void main(String[] args) {
Solution test = new Solution();
int[] nums = {1, 2, 3, 4, 5, 6, 7};
for (int i = 0; i < nums.length; i++)
System.out.print(nums[i] + ", ");
System.out.println();
test.rotate(nums, 4);
for (int i = 0; i < nums.length; i++)
System.out.print(nums[i] + ", ");
System.out.println();
}
}
参考的网站：
http://www.programcreek.com/2015/03/rotate-array-in-java/
其中有一段对于
System.arraycopy() vs. Arrays.copyOf() in Java
的分析，还不错.
http://www.programcreek.com/2015/03/system-arraycopy-vs-arrays-copyof-in-java/
这个方法也不是很巧。我想得时候想复杂了。
没什么难度。
Anyway, Good luck, Richardo!
