class Solution {
public:
int findUnsortedSubarray(vector<int>& nums) {
}
};
581. 最短无序连续子数组
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15] 输出：5 解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4] 输出：0
示例 3：
输入：nums = [1] 输出：0
提示：
1 <= nums.length <= 104-105 <= nums[i] <= 105
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
原站题解
golang 解法, 执行用时: 32 ms, 内存消耗: 6.4 MB, 提交时间: 2023-09-25 10:43:49
// 一次遍历
func findUnsortedSubarray1(nums []int) int {
n := len(nums)
minn, maxn := math.MaxInt64, math.MinInt64
left, right := -1, -1
for i, num := range nums {
if maxn > num {
right = i
} else {
maxn = num
}
if minn < nums[n-i-1] {
left = n - i - 1
} else {
minn = nums[n-i-1]
}
}
if right == -1 {
return 0
}
return right - left + 1
}
// 排序
func findUnsortedSubarray(nums []int) int {
if sort.IntsAreSorted(nums) {
return 0
}
numsSorted := append([]int(nil), nums...)
sort.Ints(numsSorted)
left, right := 0, len(nums)-1
for nums[left] == numsSorted[left] {
left++
}
for nums[right] == numsSorted[right] {
right--
}
return right - left + 1
}
javascript 解法, 执行用时: 64 ms, 内存消耗: 43.3 MB, 提交时间: 2023-09-25 10:43:02
/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function(nums) {
if (isSorted(nums)) {
return 0;
}
const numsSorted = [...nums].sort((a, b) => a - b);
let left = 0;
while (nums[left] === numsSorted[left]) {
left++;
}
let right = nums.length - 1;
while (nums[right] == numsSorted[right]) {
right--;
}
return right - left + 1;
};
const isSorted = (nums) => {
for (let i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
return false;
}
}
return true;
}
// 一次遍历
var findUnsortedSubarray = function(nums) {
const n = nums.length;
let maxn = -Number.MAX_VALUE, right = -1;
let minn = Number.MAX_VALUE, left = -1;
for (let i = 0; i < n; i++) {
if (maxn > nums[i]) {
right = i;
} else {
maxn = nums[i];
}
if (minn < nums[n - i - 1]) {
left = n - i - 1;
} else {
minn = nums[n - i - 1];
}
}
return right === -1 ? 0 : right - left + 1;
};
python3 解法, 执行用时: 76 ms, 内存消耗: 16.9 MB, 提交时间: 2023-09-25 10:42:25
class Solution:
# 一次遍历
def findUnsortedSubarray2(self, nums: List[int]) -> int:
n = len(nums)
maxn, right = float("-inf"), -1
minn, left = float("inf"), -1
for i in range(n):
if maxn > nums[i]:
right = i
else:
maxn = nums[i]
if minn < nums[n - i - 1]:
left = n - i - 1
else:
minn = nums[n - i - 1]
return 0 if right == -1 else right - left + 1
# 排序
def findUnsortedSubarray(self, nums: List[int]) -> int:
n = len(nums)
def isSorted() -> bool:
for i in range(1, n):
if nums[i - 1] > nums[i]:
return False
return True
if isSorted():
return 0
numsSorted = sorted(nums)
left = 0
while nums[left] == numsSorted[left]:
left += 1
right = n - 1
while nums[right] == numsSorted[right]:
right -= 1
return right - left + 1
java 解法, 执行用时: 1 ms, 内存消耗: 43.5 MB, 提交时间: 2023-09-25 10:41:36
class Solution {
// 排序
public int findUnsortedSubarray1(int[] nums) {
if (isSorted(nums)) {
return 0;
}
int[] numsSorted = new int[nums.length];
System.arraycopy(nums, 0, numsSorted, 0, nums.length);
Arrays.sort(numsSorted);
int left = 0;
while (nums[left] == numsSorted[left]) {
left++;
}
int right = nums.length - 1;
while (nums[right] == numsSorted[right]) {
right--;
}
return right - left + 1;
}
public boolean isSorted(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if (nums[i] < nums[i - 1]) {
return false;
}
}
return true;
}
// 一次遍历
public int findUnsortedSubarray(int[] nums) {
int n = nums.length;
int maxn = Integer.MIN_VALUE, right = -1;
int minn = Integer.MAX_VALUE, left = -1;
for (int i = 0; i < n; i++) {
if (maxn > nums[i]) {
right = i;
} else {
maxn = nums[i];
}
if (minn < nums[n - i - 1]) {
left = n - i - 1;
} else {
minn = nums[n - i - 1];
}
}
return right == -1 ? 0 : right - left + 1;
}
}
cpp 解法, 执行用时: 28 ms, 内存消耗: 26.1 MB, 提交时间: 2023-09-25 10:40:45
class Solution {
public:
// 排序
int findUnsortedSubarray1(vector<int>& nums) {
if (is_sorted(nums.begin(), nums.end())) {
return 0;
}
vector<int> numsSorted(nums);
sort(numsSorted.begin(), numsSorted.end());
int left = 0;
while (nums[left] == numsSorted[left]) {
left++;
}
int right = nums.size() - 1;
while (nums[right] == numsSorted[right]) {
right--;
}
return right - left + 1;
}
// 一次遍历
int findUnsortedSubarray(vector<int>& nums) {
int n = nums.size();
int maxn = INT_MIN, right = -1;
int minn = INT_MAX, left = -1;
for (int i = 0; i < n; i++) {
if (maxn > nums[i]) {
right = i;
} else {
maxn = nums[i];
}
if (minn < nums[n - i - 1]) {
left = n - i - 1;
} else {
minn = nums[n - i - 1];
}
}
return right == -1 ? 0 : right - left + 1;
}
};