面试常见算法——连续子序列问题
新的一周，又到了上班的日子了，由于新型肺炎病毒还在持续，有些人可能收到通知还是在家里远程办公，但是有些人可能公司就要求回去公司上班了，在这里还是要提醒大家，无论是在家也好，在公司也好都要做好防护工作。
好了回到正题，不知道大家面试的时候有没有遇到过这种问题，“最长子序列”，“最多子序列”，“连续子序列”等问题，最近刷题的时候刷到一道挺有意思的题：
题目描述
给定一个整数数组，你需要寻找一个连续的子数组，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
你找到的子数组应是最短的，请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。 输入的数组可能包含重复元素 ，所以升序的意思是<=。
题解
看到题目的第一想法是找到第一个和最后一个异常的位置，然后取差值，解释一下什么叫异常的位置：
正常情况下，数组是升序的，如果在某个位置出现降序了，那么这个位置就异常了。
示例中第一个异常的位置是 pos=1，最后一个异常的位置是 pos=5，位置找到了，但是最后我们要算个数的时候需要+1，当我满心满意写完提交的时候，傻了，wrong answer了，没有注意到题目下面还有说明，有可能会有重复的元素，如果有重复元素的话，单纯的找异常的位置是不行的，我们来看这么一个案例：
示例2:
输入：[1, 3, 2, 2, 2]
输出：4
解释：你只需要对[3, 2, 2, 2]进行升序排序
如果还按照我们上面的逻辑，第一个异常的位置是 pos=1，最后一个异常的位置是 pos=2，这样结果就错了，实际最后一个异常的位置是 pos=4；那么我们怎么去正确的找到这两个异常的位置呢？我们对数组进行一次正向遍历，先把最后一个异常的位置找出来，而且要标记当前便利过程中遇到的最大元素，这样我们可以进行比对，就比如示例2：
- 第一次：最大元素是1，最后异常位置是0（默认）
- 第二次：最大元素是3，最后异常位置是0（这时候没有发生异常）
- 第三次：最大元素是3，最后异常位置是2（首次发生异常）
- 第四次：最大元素是3，最后异常位置是3
- 第五次，最大元素是3，最后异常位置是4，遍历结束，找到最后一个异常位置
那么同理，我们再反向遍历一次，就能找到第一个异常的位置了。
代码
public int findUnsortedSubarray(int[] nums) {
if (null == nums || nums.length <= 1) {
return 0;
}
int len = nums.length;
int start = nums[0];
int end = nums[len - 1];
int left = 0; //第一个异常位置
int right = 0; //最后一个异常位置
for (int i = 0; i < len; i++) {
if (nums[i] < start) {
right = i;
} else {
start = nums[i];
}
}
for (int i = len - 1; i >= 0; i--) {
if (nums[i] > end) {
left = i;
} else {
end = nums[i];
}
}
// 如果两个异常位置相同（即都为0），那么就没有异常
if (right - left == 0) {
return 0;
}
return right - left + 1;
}本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-02-10，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录