jotting

ⓁⒸ ‧‧‧ 189. Rotate Array

Posted on | Post modified | In
旋轉陣列

189. Rotate Array

❀ Origin

Problem

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1

1
2
3
4
5
6
Input: [1,2,3,4,5,6,7] and k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2

1
2
3
4
5
Input: [-1,-100,3,99] and k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Note

  • Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
  • Could you do it in-place with O(1) extra space?

❀ 翻譯

問題

給定一個陣列，
將陣列往右旋轉 k 個階段，
其中 k 為非負數。

注意

  • 盡你可能地提出解決方式，這裏至少有 3 種不同的方式能解決這問題。
  • 你可以在時間複雜度 O(1) 額外空間的情況下做到嗎？

❀ Solution

Golang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func rotate(nums []int, k int) {
  // 取出 nums 的總長
  var lenNums int = len(nums)
  // 將 k 除與 lenNums 並取其 餘數 設為 k (steps)
  k %= lenNums
  if k == 0 {
    return
  }
  
  // nums 已 k 為範圍分前後兩部分，並將其相反 append 進 temp
  // 關於後面三個點：
  // func append(slice []Type, elems ...Type) []Type
  // append 第一個可以擺 slice，但往後則是擺和第一個 slice 一樣 Type 的 數個 value 
  // 故後面必須加上 ... 將 slice 打散後加入 append 。
  // 參照：
  // https://github.com/zhangyachen/zhangyachen.github.io/issues/137
  // https://coderwall.com/p/tlnhmg/appending-two-slices-in-go-what-s-with-that
  tmp := append(nums[lenNums-k:], nums[0:lenNums-k]...)
  
  // 將 nums 設置回去
  for index, value := range tmp {	
    nums[index] = value
  }

}