[HackerRank]幾乎完成的排序(Almost Sorted)

題目描述

給定一個擁有許多元素的整數陣列,您可以使用一次以下其中一種方式將它改變成遞增排序嗎?

交換兩個元素
反轉子陣列

原題網址

https://www.hackerrank.com/challenges/almost-sorted

輸入格式

第一行為一個整數n,表示陣列的大小。n的範圍在2到100000之間(包含2和100000)。

接下來的一行為陣列的元素,使用空格分開。元素的值在0到1000000之間(包含0和1000000),每個元素皆不相同。

輸出格式

如果陣列已經被排序,只需輸出「yes」就好。
如果您可以僅使用一個方式將其排序完成,要先輸出「yes」,接著根據您用的方式在接下來的一行繼續輸出。若您使用交換元素的方法,輸出「swap l r」,l為要左邊交換元素的位置,r為右邊交換元素的位置。若您使用反轉子陣列的方法,輸出「reverse l r」,l為子陣列最左邊元素的位置,r為子陣列最右邊元素的位置。若同時可以使用交換元素和反轉子陣列的方法,則使用交換元素的方法。

範例輸入1

2
4 2

範例輸出1

yes
swap 1 2

範例輸入2

3
3 1 2

範例輸出2

no

範例輸入3

6
1 5 4 3 2 6

範例輸出3

yes
reverse 2 5

額外解釋

第一個範例中,您可以swap(1, 2)或是reverse(1, 2)來完成排序,所以只輸出交換元素的作法。
第二個範例中,無法使用一次交換元素或是反轉陣列的方式來完成排序
第三個範例中,可以使用reverse(2, 5)來完成排序

解題概念

為了解題方便,可將原始陣列的長度改成n+2,並且在新陣列的第一個元素和最後一個元素擺上邊界,就是比最小值還要更小的值和比最大值還要更大的值。在這題目中,輸入的陣列元素範圍在0到1000000之間(包含0和1000000),所以設定新陣列的第一個元素為-1,最後一個元素為1000001。

接著從第二個元素開始,先找出陣列沒有被排序的位置r,如果陣列已經全部排序完成,直接輸出「yes」。

找到陣列沒有被排序的位置r之後,接著先嘗試使用交換元素的方式,看能不能找到一個位置l,與位置r的元素交換之後能將陣列全部排好。r和l的元素交換之後,他們相鄰的元素大小關係必須要正確,且換完之後,還需檢查其他元素是否也都排列完成。如果通過檢查,就輸出「swap l r」。

如果交換元素無法完成陣列排序的話,接下來要嘗試使用反轉子陣列的方式,看能不能在位置r之後找到一個位置l,將r到l的元素反轉後能將陣列全部排好。先找出r之後的反序陣列結束位置,接著判斷若將r和l交換之後(因為陣列要反轉),l位置的元素是否大於l-1位置的元素,r位置的元素是否小於r+1位置的元素,如果皆是,表示反轉這個陣列是正確的。接著要判斷r+1位置之後是不是還有沒有被排序的位置,若有,則陣列無法只使用一次交換元素或是反轉子陣列的方式完成排序,輸出「no」;若沒有,則輸出「reverse l r」。

參考答案

關於作者

Magic Len

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

相關文章