[HackerRank]拉里的陣列(Larry's Array)

題目描述

拉里有一串N個數字的陣列A,A={a1,a2,…,aN-1,aN},每個數字ai都是獨特不重複的。拉里想要用他的機器人排序這個陣列A,他的機器人可以不限次數地任意旋轉某3個連續相同的元素,舉例來說:ABC旋轉一次之後會變成BCA,再旋轉一次會變成CAB,再旋轉一次又會回到ABC

如果A={1,6,5,2,4,3},然後機器人旋轉了(6,5,2),A的內容就會變成{1,5,2,6,4,3}。

計算每組測試資料,並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以,輸出「YES」;如果不行,輸出「NO」。

原題網址

https://www.hackerrank.com/challenges/larrys-array

輸入格式

輸入第一行包含一個整數T,為測試資料的數量,範圍在1到10之間(包含1和10)。
接下來的的2T行,每兩行表示一組測試資料。一組測試資料的第一行是一個整數N,為A陣列的大小,範圍在3到1000之間(包含3和1000)。第二行輸入N個整數表示A陣列的內容,可以用ai來表示輸入的元素數值,數值範圍在1到N之間(包含1和N),每個元素的數值都不相同。

輸出格式

計算每組測試資料,並在新的一行輸出拉里的機器人是否可以成功排序陣列A。如果可以,輸出「YES」,否則輸出「NO」。

範例輸入

3
3
3 1 2
4
1 3 4 2
5
1 2 3 5 4

範例輸出

YES
YES
NO

額外解釋

用Aj表示每次旋轉後A陣列的內容。

測試資料1:

A0={3,1,2}→rotate(3,1,2)→A1={1,2,3}

A陣列已經排序好了,因此輸出「YES」。

測試資料2:
A0={1,3,4,2}→rotate(3,4,2)→A1={1,4,2,3}
A1={1,4,2,3}→rotate(4,2,3)→A2={1,2,3,4}
A陣列已經排序好了,因此輸出「YES」。

測試資料3:
沒有辦法將A陣列排序好,輸出「NO」。

解題概念

可以把這題所用到的演算法,當作是氣泡排序法(Bubble Sort)的改版。原始的氣泡排序法一次旋轉兩個元素,而這裡用到的演算法一次需旋轉三個元素。我們可以從第一個元素(陣列索引0)開始,由陣列的最尾端開始往前旋轉,把最小的數值旋轉至第一個元素的位置。接著再從第二個元素(陣列索引1)開始,由陣列的最尾端開始往前旋轉,把最小的數值旋轉至第二個元素的位置,如此一來就可以完成這三旋轉的氣泡排序法

至於該如何判斷這三旋轉的氣泡排序法是否排序成功,只需要在排到最後時,判斷最後兩個元素的順序是否正確即可,因為在這最後兩個元素之前的元素都已經確定排序好了。

參考答案

關於作者

Magic Len

各位好,我是Magic Len,是這網站的管理員。我是台灣台中大肚山上人,畢業於台中高工資訊科和台灣科技大學資訊工程系,曾在桃機航警局服役。我熱愛自然也熱愛科學,喜歡和別人分享自己的知識與經驗。如果你有興趣認識我,可以加我的Facebook,並且請註明是從MagicLen來的。

相關文章