581. 最短无序连续子数组

Posted on | In
Words count in article: 275 | Reading time ≈ 1

题目

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

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

示例1：

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

说明：

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

解法

解法一：

将原数组拷贝一份，排序。然后从头和从尾部分别遍历，找到不同的子序列即可。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] numOfCopy = Arrays.copyOf(nums, nums.length);
        Arrays.sort(nums);
        int begin = -1;
        for (int i = 0;i < nums.length;i++) {
        	if (nums[i] != numOfCopy[i]) {
        		begin = i;
        		break;
        	}
        }
        
        int end = -1;
        for (int i = nums.length - 1;i >= 0;i--) {
        	if (nums[i] != numOfCopy[i]) {
        		end = i;
        		break;
        	}
        }
        
        if (begin == -1 || end == -1) {
        	return 0;
        }
        
        return end - begin + 1;
    }
}
0%