110 - 581 最短无序连续子数组

题目

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

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

示例 1:

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

说明 :

• 输入的数组长度范围在 [1, 10,000]。

• 输入的数组可能包含重复元素 ，所以升序的意思是<=。

解答

双指针

最简单的方法应该就是比大小了。。双指针定大小

var findUnsortedSubarray = function(nums) {
  let left = nums.length,
    right = 0
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[j] < nums[i]) {
        right = Math.max(right, j)
        left = Math.min(left, i)
      }
    }
  }
  return right - left < 0 ? 0 : right - left + 1
}

Runtime: 1356 ms, faster than 5.00% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.

Memory Usage: 36.7 MB, less than 87.50% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.

可惜效率极低

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func findUnsortedSubarray(nums []int) int {
    left, right := len(nums), 0
    for i := 0; i < len(nums)-1; i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[j] < nums[i] {
                right = max(right, j)
                left = min(left, i)
            }
        }
    }
    if right-left < 0 {
        return 0
    } else {
        return right - left + 1
    }
}

Runtime: 1220 ms, faster than 5.43% of Go online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Shortest Unsorted Continuous Subarray.

go也效率极慢

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        left = len(nums)
        right = 0
        for I in range(len(nums) - 1):
            for j in range(I + 1, len(nums)):
                if nums[j] < nums[I]:
                    right = max(right, j)
                    left = min(left, i)
        return 0 if (right - left < 0) else (right - left + 1)

python直接超时。。

排序

排序，然后比较不同的地方，就是答案了

var findUnsortedSubarray = function(nums) {
  const sorted = nums.slice(0);
  sorted.sort((a, b) => a - b)
  let start = sorted.length,
    end = 0
  for (let i = 0; i < sorted.length; i++) {
    if (sorted[i] != nums[i]) {
      start = Math.min(start, i)
      end = Math.max(end, i)
    }
  }
  return (end - start >= 0 ? end - start + 1 : 0)
}

Runtime: 96 ms, faster than 58.10% of JavaScript online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 39.3 MB, less than 12.50% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func findUnsortedSubarray(nums []int) int {
    sorted := make([]int, len(nums))
    copy(sorted, nums)
    sort.Ints(sorted)
    start := len(sorted)
    end := 0
    for i, val := range sorted {
        if val != nums[i] {
            start = min(start, i)
            end = max(end, i)
        }
    }
    if end-start >= 0 {
        return end - start + 1
    } else {
        return 0
    }
}

Runtime: 44 ms, faster than 26.36% of Go online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 6.1 MB, less than 100.00% of Go online submissions for Shortest Unsorted Continuous Subarray.

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        sort = nums.copy()
        sort.sort()
        start = len(sort)
        end = 0
        for i in range(len(sort)):
            if sort[i] != nums[i]:
                start = min(start, i)
                end = max(end, i)
        return 0 if (end - start < 0) else (end - start + 1)

Runtime: 256 ms, faster than 41.83% of Python3 online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 15.1 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.

双指针的另一种做法

作者：XiaoBaik 链接：https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/zong-jie-liao-san-chong-xiang-fa-by-xiaobaik/

var findUnsortedSubarray = function(nums) {
  let start = -1,
    end = -2,
    min = nums[nums.length - 1],
    max = nums[0]
  for (let i = 0; i < nums.length; i++) {
    let pos = nums.length - 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
}

Runtime: 68 ms, faster than 86.38% of JavaScript online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 37.1 MB, less than 75.00% of JavaScript online submissions for Shortest Unsorted Continuous Subarray.

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        start = -1
        end = -2
        min_val = nums[len(nums) - 1]
        max_val = nums[0]
        for i in range(len(nums)):
            pos = len(nums)-1-i
            max_val = max(max_val, nums[i])
            min_val = min(min_val, nums[pos])
            if(nums[i] < max_val):
                end = i
            if(nums[pos] > min_val):
                start = pos
        return end-start+1

Runtime: 276 ms, faster than 22.72% of Python3 online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 15.2 MB, less than 5.00% of Python3 online submissions for Shortest Unsorted Continuous Subarray.

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}
func findUnsortedSubarray(nums []int) int {
    start := -1
    end := -2
    min_val := nums[len(nums)-1]
    max_val := nums[0]
    for i, val := range nums {
        pos := len(nums) - 1 - i
        max_val = max(max_val, val)
        min_val = min(min_val, nums[pos])
        if val < max_val {
            end = i
        }
        if nums[pos] > min_val {
            start = pos
        }
    }
    return end - start + 1
}

Runtime: 36 ms, faster than 55.81% of Go online submissions for Shortest Unsorted Continuous Subarray. Memory Usage: 6.2 MB, less than 100.00% of Go online submissions for Shortest Unsorted Continuous Subarray.