Leetcode No.581( Shortest Unsorted Continuous Subarray) 心得
題目:
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.Note:
- Then length of the input array is in range [1, 10,000].
- The input array may contain duplicates, so ascending order here means <=.
想法:
第一個想法是先 sort array,然後再和原本array比較,這個速度就取決於 sort array 的方法。再來發現題目只是要找哪一個”連續”區域需要 sort,也就是在這個連續區域外,左邊和右邊都是分別排序好的,由小到大。
因此,我可以從最左邊開始檢查,如果發現有個值比目前找到排序好得最後的值更小,那就去比較這個值應該是要放入哪個位置,也就是應該要被排序的區域至少要從那個位置開始,並且記錄這個值為基準值繼續往下比較。
最右邊開始檢查的方法同上。最後就是兩個 index 相減 + 1 算出應該要 re-sort區域有幾個數字。
Ex: [2, 4, 6, 8, 14, 12, 7,16, 18, 20]
Step1: [2, 4, 6, 8, 14] 順利檢查通過,index = 4, checkValue = 14;
Step2: 12 不合規則,往前比較只到14,index =4, checkValue = 12;
Step3: 7 不合規則,往前比較到8,index =3, checkValue = 7;
這部分要注意比較到不合規則前的處理和之後比較到不合規則處理會有一點不同,因為在發生不合規則前 index 和 checkValue 是要一直更新的。比較到不合規則後,則是發生不合規則才需要更新。
還要注意 array size = 0 和 1 的情形。目前這邊我是 hard code 回傳 0。
# 我的程式在前12% ^____^
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int CurrentMin, CurrentMax, indexMin, indexMax;
bool MinFail = false, MaxFail = false;
int size = nums.size();
CurrentMin = nums[0];
indexMin = 0;
CurrentMax = nums[size — 1];
indexMax = size — 1;
if (size == 0 || size == 1) return 0;for (int index = 1; index < size; index++) {
if (CurrentMin > nums[index]) {
MinFail = true;
CurrentMin = nums[index];
for (int reverse = indexMin — 1; reverse >= 0; reverse — ) {
if (nums[reverse] > CurrentMin) {
indexMin = reverse;
}
else
break;
}
} else if (MinFail == false) {
indexMin = index;
CurrentMin = nums[index];
}
}for (int index = size — 2; index >= 0; index — ) {
if (CurrentMax < nums[index]) {
MaxFail = true;
CurrentMax = nums[index];
for (int reverse = indexMax + 1; reverse < size; reverse++) {
if (nums[reverse] < CurrentMax) {
indexMax = reverse;
}}
} else if (MaxFail == false) {
indexMax = index;
CurrentMax = nums[index];
}
}
int result = indexMax — indexMin + 1;
if (result <= 0)
return 0;
else
return result;
}
};
網路上解法:
差不多和我的一樣,有個解法的改良方法不錯。
先從前面找出順序的終點,然後從這個終點和 array 最後之間,找到 Min,再找出順序的區塊中這個 Min 應該在的位置。
Max的方法同上。
