581 Shortest Unsorted Continuous Subarray

wenyiweb 发布于2019-08-15 13:55 / 1614人阅读

摘要：如果数组是乱序的，我们就要找出这个数组的最小子数组，以满足，只要排序好这个子数字，整个数字就是有序的。我们用一个变量来保存遍历过的元素中的最大值，用一个变量来保存从数组尾部遍历的元素中的最小值。

题目详情

Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.

题目的意思是输入一个数组，这个数组可能是排序好的，也可能是乱序的。如果数组是乱序的，我们就要找出这个数组的最小子数组，以满足，只要排序好这个子数字，整个数字就是有序的。

Example 1:
Input: [2, 6, 4, 8, 10, 9, 15]
Output: 5
Explanation: 只需要排序[6,4,8,10,9]就可以保证整个数组的有序

思路

大体思路是这样的：如果当前元素比它前面的元素中的最大的值小，那它就在待排序的子数组里；如果当前元素比它后面元素中的最小值要大，那它也需要包含在待排序的子数组里。

我们用一个变量（max）来保存遍历过的元素中的最大值，用一个变量(min)来保存从数组尾部遍历的元素中的最小值。

然后我们只要通过遍历找到，最后一位待排序元素和最前面的待排序元素就可以了。

解法

    public int findUnsortedSubarray(int[] nums) {
        int length = nums.length;
        int start =-1 ;
        int end = -2;
        int min = nums[length-1];
        int max = nums[0];
        
        for(int i=1;i min){
                start = length-1-i;
            }
        }
        return end-start+1;
    }

GPU云服务器云服务器 Unsorted Continuous subarray Shortest

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/68397.html

leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
[LeetCode] 862. Shortest Subarray with Sum at Leas

摘要：较早放入的元素在队列顶部最近放入的元素在队列尾部检查最近放入的，保证队列中新放入的及对应的均为递增反证若保留，那么在下面第二个循环，该元素有可能中断循环，并使得我们无法得到队列更左边的最优解检查较早放入的最小距离 Problem Return the length of the shortest, non-empty, contiguous subarray of A with sum...

thursday 2019-08-16 13:50 评论0 收藏0
[LeetCode] 523. Continuous Subarray Sum

Problem Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sum...

stackfing 2019-08-16 13:46 评论0 收藏0
[LeetCode] 560. Subarray Sum Equals K

Problem Given an array of integers and an integer k, you need to find the total number of continuous subarrays whose sum equals to k. Example 1: Input:nums = [1,1,1], k = 2 Output: 2 Note:The length o...

ccj659 2019-08-16 13:30 评论0 收藏0