题目描述
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.
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.
解题思路
- 遍历整个序列
- 建立一个排好序的辅助数组
- 设置两个指针，begin，end
- begin从前往后扫，如果与排序后的辅助数组不相等计入当前的位置，这样begin最后的数值为，最后一个不相等的位置
- end从从后往前扫，类似begin，这样end最后的数值为，第一个不相等的位置
- 最后相减+1，即为中间隔的元素的个数
- 注意如果begin，end位置没变，证明给的数组本身是有序的，需要特殊判断一下
C++代码
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int res = 0;
if(nums.size() == 0){
return 0;
}
vector<int> v(nums); // 拷贝构造函数，复制一个nums元素一致的向量v
sort(v.begin(), v.end());
int pos = 0;
int end = v.size() - 1;
for(int i = 0; i < v.size(); i++){
if(nums[i] != v[i]){
pos = i;
}
}
for(int i = end; i >= 0; i--){
if(nums[i] != v[i]){
end = i;
}
}
if(end != v.size() - 1 && pos != 0){
res = abs(end - pos) + 1;
}
return res;
}
};
2020年0204日 解题思路
- 首先还是根据原始数组建立一个辅助数组
- 对辅助数组进行排序后，然后进行对比
- 如果排序后的数组跟原始数组是一样的，那么直接返回0即可
- 这时候，使用两个指针来表示，看不等的具体位置
- 最后 结果为 右指针的位置 - 左指针的位置 + 1 即为中间的元素过程
C++代码
class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
int res = 0;
vector<int> temp(nums);
sort(temp.begin(), temp.end());
if(temp == nums){
return 0;
}
int left = 0, right = nums.size() - 1;
while(nums[left] == temp[left]){
left++;
}
while(nums[right] == temp[right]){
right--;
}
return right - left + 1;
}
};
