**
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得理解好赠涮。是用來移動的步數(shù)。如果移動的范圍超出了右邊的limit暗挑，那么就接著從左邊開始移動笋除。很類似于圖像處理時(shí)算的neighbour。也需要進(jìn)行這樣的映射炸裆。
那么一定存在這么一個點(diǎn)垃它，他的左邊全部是可以正常移動相應(yīng)的k，而這個點(diǎn)已經(jīng)這個點(diǎn)的右邊晒衩，移動k步后都會轉(zhuǎn)到左邊嗤瞎。
所以必須找到這個點(diǎn)，我設(shè)為听系，sentinel.
找到了之后贝奇，就進(jìn)行判斷被，小于他的正常移動靠胜。大于等于他的掉瞳，正常移動后再減去一個數(shù)組長度就到左邊去了。
但是這次作業(yè)有兩個問題需要注意浪漠。
1.k是可以任意大的陕习，也就是說可以大于數(shù)組長度。因?yàn)榭梢匀我庖苿硬綌?shù)址愿。所以该镣，必須首先對k進(jìn)行處理。 k = k % nums.length;
2.我們要明白這個方法是干什么的响谓。我們傳進(jìn)來一個數(shù)組的引用损合，然后處理，再返回娘纷。
一開始嫁审，處理完后，我直接
nums = temp;
以為這樣就可以直接指向這個處理好的數(shù)組了赖晶。的確也是如此律适。
**
但是，這是錯的遏插。
仔細(xì)回想下C語言里面學(xué)的函數(shù)調(diào)用時(shí)棧的結(jié)構(gòu)捂贿。Java類似。
我們在main函數(shù)中傳入nums時(shí)胳嘲，會拷貝一份指向nums的引用眷蜓，存放在方法rotate的活動空間上。所以胎围，如果傳入的直接就是數(shù)（int,double,float...）吁系，我們在活動區(qū)間修改這些傳入?yún)?shù)是不會影響到原數(shù)據(jù)的德召。這就是所謂的改變形參不會改變實(shí)參。
但是這里不同汽纤，傳入的是地址上岗，或者說，指向數(shù)組的一個指針蕴坪。
所以我們可以通過修改這個指針指向的內(nèi)容肴掷，而達(dá)到修改實(shí)參的效果。
但是背传，我又犯了一個錯誤呆瞻。我以為nums = temp；就可以修改實(shí)參了径玖。
其實(shí)是大錯特錯的痴脾。
因?yàn)樵谀菈K內(nèi)存位置處，我拷貝的是指向?qū)崊ums的地址∈嵝牵現(xiàn)在我把該地址抹掉赞赖，存入指向temp的地址。那么冤灾，原nums的數(shù)據(jù)發(fā)生改變了嗎前域？
沒有。因?yàn)槲覀冊诜椒╮otate中進(jìn)行的操作沒有返回到實(shí)參中韵吨。
所以匿垄，必須得將temp數(shù)組再重新拷貝給nums
**
這道題，我多設(shè)了一個數(shù)組來進(jìn)行處理归粉。這是上普林斯頓算法課時(shí)椿疗，老師在講 merge sort時(shí)給我的靈感。所以說盏浇，那些課的東西還是有用的。
**
總結(jié)下：
1.k要注意可以隨意大小
2.在方法中芽狗，如何修改實(shí)參的內(nèi)容
之前學(xué)習(xí)的C語言绢掰，對于了解Java還是很有用的。正如我現(xiàn)在學(xué)習(xí)Java童擎，了解OOP滴劲，然后學(xué)校的C++考試我其實(shí)就沒有那么虛了。
**
發(fā)現(xiàn)LJ有種讓人欲罷不能的感覺顾复。也許也是因?yàn)閷?shí)在不想學(xué)習(xí)電氣的緣故吧班挖。。芯砸。
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();
}
}
參考的網(wǎng)站：
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/
這個方法也不是很巧双揪。我想得時(shí)候想復(fù)雜了动羽。
沒什么難度。
Anyway, Good luck, Richardo!
