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.
今天的 Daily 比較簡單，
所以我們來做上週的週賽第三題。
題目給我們一個一維 nums，
長度為 N，裡面會有 0 ~ n - 1號元素。
題目需求是把 nums 改成 0 起始的遞增陣列，
可以透過兩個操作來實現：
- 向左循環移動一格
- 把陣列全部反轉
請問最少需要幾個操作才能達成目的。
這題要有一個觀念才能繼續做下去：
- 向左循環永遠不會改變陣列順序
所以如果一開始就是逆序的，肯定要一次反轉，
我們要分成先反轉再向左移、先向左移再反轉。
比較麻煩的是正序，
我一開始以為正序只要考慮現在 0 的 index i 到 index 0 的距離，
但小問題，在 nums 後半段的 0 可以透過反轉兩次 + 向左循環跨越實現更小的操作次數。
舉例 nums = 2 3 4 5 6 0 1
如果不反轉兩次，答案會是 5；
如果反轉兩次會是：
狀態 操作次數
1 0 6 5 4 3 2 -> 1
6 5 4 3 2 1 0 -> 3
0 1 2 3 4 5 6 -> 4
所以我們要計算 0 的 index i 到 n - 1 的距離，
然後加上至少三次（反轉兩次、向左移一次） == n - 1 + 3 來比較操作次數。
這樣我們正逆序都各有兩種路徑，一共四種路徑比較取最小值即可。
今天程式碼太長了先不放。
計算複雜度：O(N)
空間複雜度：O(1)
Github程式碼：
