陣列迴旋位移 (Array rotation)


提交答案

分數: 100 (部分)
時間限制: 1.0s
記憶體限制: 128M

作者:
題目類型
允許的語言
C, C++, ZIG

設計一個程式將陣列中的元素做迴旋位移

寫一個可將大小為n的陣列arr[]往左迴旋位移位移d個元素的涵式rotate(arr[], d, n)

Array before rotation

假設上述陣列往左做迴旋位移2個元素後,會得到下方陣列。

Array after rotation by 2

方法1 (Using temp array)

假設輸入為 arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7

  1. d 個元素存在一個站存陣列 temp

    temp[] = [1, 2]

  2. 將原本陣列 arr[] 做位移

    arr[] = [3, 4, 5, 6, 7, 6, 7]

  3. 將暫存陣列 temp[] 中的 d 個元素貼回 arr[] 陣列的尾端。

    arr[] = [3, 4, 5, 6, 7, 1, 2]

方法2 (逐一處理每個元素)

leftRotate(arr[], d, n)
start
  For i = 0 to i < d
    Left rotate all elements of arr[] by one
end

要逐一處理各個元素,先將arr[0]存到一個暫存變數temp、然後將arr[1]移到arr[0], arr[2]移到arr[1], \ldots, 最後再將temp移到arr[n-1]

arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2為例子:

arr[]往左迴旋位移1個元素做2次,

第一次迴旋位移後會得到[2, 3, 4, 5, 6, 7, 1],第二次迴旋位移後會得到[ 3, 4, 5, 6, 7, 1, 2]

任務

你將完成可以把大小為n的陣列arr[]往左迴旋位移d個位子的leftRotate涵式。涵式宣告如下:

 void leftRotate(int arr[], int d, int n) 
 {
     /* 你的程式碼 */
 }

留言

目前沒有評論。