内容
给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。
你找到的子数组应是最短的,请输出它的长度。
示例 1:
输入: [2, 6, 4, 8, 10, 9, 15]
输出: 5
解释: 你只需要对 [6, 4, 8, 10, 9] 进行升序排序,那么整个表都会变为升序排序。
说明 :
输入的数组长度范围在 [1, 10,000]。
输入的数组可能包含重复元素 ,所以升序的意思是<=。
思路
将原数组复制一份,然后升序排序,再对比原数组,从最左边和最右边开始遍历,如果碰到第一个下标中值不同,那么分别就是这个子序列的开头下标和结尾下标。
代码
/**
* @param {number[]} nums
* @return {number}
*/
var findUnsortedSubarray = function (nums) {
var nums2 = nums.slice(0);
nums2.sort(function (a, b) {
return a - b;
})
var start = -1,
end = -1;
for (var i = 0, j = nums.length - 1; i < nums.length; i++, j--) {
if (start == -1 && nums[i] != nums2[i]) {
start = i;
}
if (end == -1 && nums[j] != nums2[j]) {
end = j;
}
}
return end - start == 0 ? 0 : end - start + 1;
};
网友评论