美文网首页
581. 最短无序连续子数组

581. 最短无序连续子数组

作者: 吃饭用盘装 | 来源:发表于2018-06-05 19:47 被阅读49次

    内容

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

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

    示例 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;
    };
    

    回到目录

    相关文章

      网友评论

          本文标题:581. 最短无序连续子数组

          本文链接:https://www.haomeiwen.com/subject/ivmmsftx.html