You are given an integer array nums of length n, where nums is a permutation of the integers from 0 to n - 1.
You may perform only the following operations:
Reverse the entire array.
Rotate Left by One: Move the first element to the end of the array, and rest elements to left by one position.
Return an integer denoting the minimum number of operations required to sort the array in increasing order. If it is not possible to sort the array using only the given operations, return -1.
Example 1:
Input: nums = [0,2,1]
Output: 2
Explanation:
Rotate Left by one: [2, 1, 0]
Reverse the array: [0, 1, 2]
The array becomes sorted in 2 operations, which is minimal
Example 2:
Input: nums = [1,0,2]
Output: 2
Explanation:
Reverse the array: [2, 0, 1]
Rotate Left by one: [0, 1, 2]
The array becomes sorted in 2 operations, which is minimal.
Example 3:
Input: nums = [2,0,1,3]
Output: -1
Explanation:
It is impossible to reach [2, 0, 1, 3]. Thus, the answer is -1.
Constraints:
1 <= n == nums.length <= 10^5
0 <= nums[i] <= n - 1
nums is a permutation of integers from 0 to n - 1.
今天這題前陣子解過,但還是卡了一下。
這題給我們一個一維陣列 nums,
nums 由 0 ~ n - 1 的數組成,長度為 N。
題目說我們可以做兩個操作來計算結果:
- 把最左側元素推到最右側
- 整個陣列左右反轉
請問最少要做幾個操作才能夠把 nums 做成 0-indexed 的遞增陣列?
這題可以利用由 0 ~ n - 1 的數組成、長度為 N的特性,
往左移與反轉陣列在 rotate 的情況下都不影響順序,
所以我們只要確認當前陣列是遞增或是遞減,
影響最後在最小值(下限,因為遞減要翻轉)要不要 + 1。
舉個例子,nums = [4 0 1 2 3]
這是遞增陣列,有兩種選擇:
- 左移
- 先翻轉再左移,再翻轉(適用起點 0 靠右半邊的位置)
但我們不知道是哪種,所以兩種都算。
假設 k 是 nums[0] 的情況下,
左移要 n - k 次操作、先翻轉要 1 + k + 1 == k + 2 次操作
遞減也可以這樣推。
C++程式碼:

計算複雜度:O(N)
空間複雜度:O(1)
Github程式碼:
MurMur:
算題目還是要有紙筆,腦子或是打字還是記不了太多,
推薦腦子跟我一樣沒那麼聰明的人,刷題多一本計算紙會順利很多 ODO

