題目來源:力扣(LeetCode)
鏈接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray
給定一個整數(shù)數(shù)組沫换,你需要尋找一個連續(xù)的子數(shù)組涛救,如果對這個子數(shù)組進行升序排序仙辟,那么整個數(shù)組都會變?yōu)樯蚺判颉?/p>
你找到的子數(shù)組應是最短的,請輸出它的長度焙蹭。
示例 1:
輸入: [2, 6, 4, 8, 10, 9, 15]
輸出: 5
解釋: 你只需要對 [6, 4, 8, 10, 9] 進行升序排序,那么整個表都會變?yōu)樯蚺判颉?
說明 :
- 輸入的數(shù)組長度范圍在 [1, 10,000]须教。
- 輸入的數(shù)組可能包含重復元素 嗜闻,所以升序的意思是<=。
冒泡法:
class Solution {
public int findUnsortedSubarray(int[] nums) {
int right = 0;
int left = 1;
for(int i=nums.length-2;i>=0;i--){
if(nums[i] > nums[i+1]){
int tmp = up(nums,i);
right = Math.max(right,tmp);
left = i;
}
}
return right-left+1;
}
private int up(int[] nums,int index){
while(index < nums.length-1){
if(nums[index] > nums[index+1]){
int tmp = nums[index+1];
nums[index+1] = nums[index];
nums[index] = tmp;
index++;
}else{
break;
}
}
return index;
}
}