581 Shortest Unsorted Continuous Subarray 最短無序連續(xù)子數(shù)組
Description:
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:
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 <=.
題目描述:
給定一個整數(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)樯蚺判颉?/p>
說明 :
輸入的數(shù)組長度范圍在 [1, 10,000]猿推。
輸入的數(shù)組可能包含重復元素 ，所以升序的意思是<=照卦。
思路:
- 排序之后比較位置差別
時間復雜度O(nlgn), 空間復雜度O(1) - 設(shè)置兩個指針分別指向數(shù)組的最大值和最小值, 初始值設(shè)為 0和 -1保證數(shù)組有序的時候輸出 0
時間復雜度O(n), 空間復雜度O(1)
代碼:
C++:
class Solution
{
public:
int findUnsortedSubarray(vector<int>& nums)
{
int len = nums.size(), start = 0, end = -1, min_nums = nums[len - 1], max_nums = nums[0];
for (int i = 0, pos = 0; i < len; i++)
{
pos = len - 1 - i;
max_nums = max(max_nums, nums[i]);
min_nums = min(min_nums, nums[pos]);
if (nums[i] < max_nums) end = i;
if (nums[pos] > min_nums) start = pos;
}
return end - start + 1;
}
};
Java:
class Solution {
public int findUnsortedSubarray(int[] nums) {
int len = nums.length, start = 0, end = -1, min = nums[len - 1], max = nums[0];
for (int i = 0, pos = 0; i < len; i++) {
pos = len - 1 - i;
max = Math.max(max, nums[i]);
min = Math.min(min, nums[pos]);
if (nums[i] < max) end = i;
if (nums[pos] > min) start = pos;
}
return end - start + 1;
}
}
Python:
class Solution:
def findUnsortedSubarray(self, nums: List[int]) -> int:
return len([i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b]) and [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b][-1] - [i for i, (a, b) in enumerate(zip(nums, sorted(nums))) if a != b][0] + 1
