未分類

Rotate Array

Array, Go, LeetCode

Rotate Array

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.

提示 解題應用
Array Array/Slice

Default:

1
2
3
func rotate(nums []int, k int)  {
}

解答思路:

之所以這題沒有一個回傳值是因為要你乖乖的做陣列的位移，否則如果是一般有腳本語言特性的程式語言大概一行便能搞定了吧!因為只是回傳該陣列的嫁接罷了(array[起始index:長度])，所以必需要幫array的每一個值做移動，雖然至少有三種以上的方式可以完成，不過目前還是暫時只寫想到的其中一種，總之就是先記錄陣列中的最後一個值，接著在開始將元素一個個向後取代，之到結束才將剛剛存的最後一個值放入第一個，再看總共需要重覆做幾次上述的動作即可。

程式碼解說:

正如先前所說，第一個迴圈用來計算共需重覆做多少次向右位移，而在第二個迴圈開始將一個個值向後移動取代之前，先將陣列最後一個值取出暫存以防止被覆蓋，最後在全部位移完畢後，才將暫存的最後一個值放入index為0的位置

1
2
3
4
5
6
7
8
9
var last int
length := len(nums)
for i := 1; i <= k; i++ {
	last = nums[length-1]
	for j := length - 2; j >= 0; j-- {
		nums[j+1] = nums[j]
	}
	nums[0] = last
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
func rotate(nums []int, k int) {
	var last int
	length := len(nums)
	for i := 1; i <= k; i++ {
		last = nums[length-1]
		for j := length - 2; j >= 0; j-- {
			nums[j+1] = nums[j]
		}
		nums[0] = last
	}
}

總結:

遇到需要將陣列向右位移(旋轉)的狀況時，先將陣列中最後一個值給暫存起來，接著才一個個將往後做取代，完成之後才將暫存的值放入陣列的第一個，最後再依題目共需要做幾次位移重覆上述的動作。

分享到