陣列迴旋位移 (Array rotation)
設計一個程式將陣列中的元素做迴旋位移
寫一個可將大小為的陣列arr[]
往左迴旋位移位移個元素的涵式rotate(arr[], d, n)
。
假設上述陣列往左做迴旋位移2個元素後,會得到下方陣列。
方法1 (Using temp array)
假設輸入為 arr[] = [1, 2, 3, 4, 5, 6, 7]
, ,
將 個元素存在一個站存陣列
temp
。temp[] = [1, 2]
將原本陣列
arr[]
做位移arr[] = [3, 4, 5, 6, 7, 6, 7]
將暫存陣列
temp[]
中的 個元素貼回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]
, , 最後再將temp
移到arr[n-1]
。
以arr[] = [1, 2, 3, 4, 5, 6, 7]
, 為例子:
將arr[]
往左迴旋位移1個元素做次,
第一次迴旋位移後會得到[2, 3, 4, 5, 6, 7, 1]
,第二次迴旋位移後會得到[ 3, 4, 5, 6, 7, 1, 2]
。
任務
你將完成可以把大小為n
的陣列arr[]
往左迴旋位移個位子的leftRotate
涵式。涵式宣告如下:
void leftRotate(int arr[], int d, int n)
{
/* 你的程式碼 */
}
留言