0581._Shortest_Unsorted_Continuous_Subarray

发表于 分类于 ， ，

581. 最短无序连续子数组

难度: Easy

刷题内容

原题连接

内容描述

给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。

你找到的子数组应是最短的，请输出它的长度。

示例1:

 输入: [2, 6, 4, 8, 10, 9, 15]
 输出: 5
 解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。

说明 :

  1. 输入的数组长度范围在 [1, 10,000]。
  2. 输入的数组可能包含重复元素 ，所以升序的意思是<=。

解题方案

思路 1
**- 时间复杂度: O(1)**- 空间复杂度: O(N)**

省空间的算法，但是耗时间

每次循环，如果当前数组的第一位是最小值，则将其“弹出”；如果最后一位是最大值，则也将其“弹出”；如果以上两种情况都没有，则说明剩下的数组是最短无序连续子数组

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number[]} nums
 * @return {number}
 */
var findUnsortedSubarray = function(nums) {
  while (nums.length) {
    if (nums[0] === Math.min(...nums)) {
      nums.shift()
    } else if (nums[nums.length - 1] === Math.max(...nums)) {
      nums.pop()
    } else {
      return nums.length
    }
  }
  return nums.length
};

思路 2
**- 时间复杂度: O(1)**- 空间复杂度: O(2N)**

省时间的算法，但是耗空间

与上面方法比较，不用每次都计算最大值和最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var findUnsortedSubarray = function(nums) {
  const newNums = [...nums]
  nums.sort((a, b) => (a - b))
  let startIndex = 0
  let endIndex = 0
//   正向查找
  for (let i = 0; i < newNums.length; i++) {
    if (nums[0] === newNums[i]) {
      nums.shift()
    } else {
      break
    }
  }
//  逆向查找
  for (let j = newNums.length - 1; j > 0; j--) {
    if (nums[nums.length - 1] === newNums[j]) {
      nums.pop();
    } else {
      break
    }
  }
  return nums.length;
};