文档章节

最短无序连续子数组 Shortest Unsorted Continuous Subarray

叶枫啦啦
 叶枫啦啦
发布于 2017/05/15 20:42
字数 841
阅读 86
收藏 0

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: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.

Note:

  1. Then length of the input array is in range [1, 10,000].
  2. The input array may contain duplicates, so ascending order here means <=.

解决方案:

①自己编写,用时59ms。思路:将数组复制到一个新的数组,对新的数组进行排序,分别从头部和尾部扫描数组,若有不同则立即停止,记录下出现不同的位置,两者的差值加1的到子数组的长度。注意数组的边界值。实现代码如下:

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int len = 0;
        int start = 0;
        //初始若为0,则需要注意两数组相同时长度为0
        int end = 0;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        for(int i = 0; i <= nums.length-1 ; i ++){
            if(nums[i] != arr[i]){
                start = i;
                break;
            }
        }
        for(int i = nums.length - 1; i >= 0 ; i --){
            if(nums[i] != arr[i]){
                end = i;
                break;
            }
        }
        if(end != 0){
            len = end - start + 1;
            return len;
        }
        return 0;
    }
}

②之后,在discuss部分找到了同一个思路但是更为简洁的方法,38ms:

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int start = arr.length;//注意起始位置!!
        int end = 0;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }
}

以上两种方法的时间复杂度为:O(nlogn),为数组排序的时间。空间复杂度为 O(n),因为对数组进行了复制。

③第三种方法是使用栈(95ms),只要数值大于前一个将下标从0依次入栈,因为此时都是升序,当遇到第一个降序时,就是我们要找的start,此时只要pop()出该下标值即可,因为是从头到尾遍历,我们只要找到下标最小的一个即可。同理可以找到end。

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        Stack < Integer > stack = new Stack < Integer > ();
        int start = nums.length;
        int end = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] > nums[i])
                start = Math.min(start, stack.pop());
            stack.push(i);
        }
        stack.clear();
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i])
                end = Math.max(end, stack.pop());
            stack.push(i);
        }
        return end - start > 0 ? end - start + 1 : 0;
    }
}

时间复杂度:O(n),for循环 空间复杂度:O(n),最多入栈n个。

④ 采用四个指针,start,end,max,min,初始时,start=nums.length,end=-1,max=nums[0],min=nums[1]然后将end和max指针从头到尾扫描,使max指向最大值,而end指向无序数列最后一个值。同理,从尾到头扫描得到min和start的值。耗时21ms.

public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        if(nums.length < 2) return 0;
        int end = -1;
        int start = nums.length;
        int max = nums[0];
        int min = nums[nums.length-1];
        for (int i = 0;i < nums.length ;i ++ ) {
            if(nums[i] >= max){//按照顺序排序的
                max = nums[i];
            }else{//不按照顺序排序的
                end = i;
            } 
        }
        if(end == -1) return 0;//不能忘记判断,否则顺序都正确时会出错
        for (int i = nums.length - 1;i >= 0 ;i -- ) {
            if(nums[i] <= min){//按照顺序排序的
                min = nums[i];
            }else{//不按照顺序排序的
                start = i;
            }
        }
        //end和start指向的并集,即为无序列
        return end - start + 1;
    }
}

© 著作权归作者所有

叶枫啦啦
粉丝 13
博文 583
码字总数 400448
作品 0
海淀
私信 提问
[LeetCode]Longest Continuous Increasing Subsequence 最长连续增长序列

链接:https://leetcode.com/problems/longest-continuous-increasing-subsequence/description/ 难度:Easy 题目:674. Longest Continuous Increasing Subsequence Given an unsorted arra......

繁著
2017/12/08
0
0
LeetCode 581. Shortest Unsorted Continuous Subarray (最短的未排序连续子阵列)

原题 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 or......

dby_freedom
2018/12/19
0
0
Leetcode 581. Shortest Unsorted Continuous Subarray

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. Description 2. Solution Version 1 Version 2 Reference https://leetcode.com/problems/shortest-unsorted-continuous-subarray/des......

SnailTyan
2018/08/28
0
0
LeetCode算法题-Shortest Unsorted Continuous Subarray(Java实现)

这是悦乐书的第267次更新,第281篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第134题(顺位题号是581)。给定一个整数数组,找到一个连续的子数组,按升序对该子数组进行排...

小川94
03/05
0
0
581. Shortest Unsorted Continuous Subarray

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, ......

什么都没想到
2017/11/08
5
0

没有更多内容

加载失败,请刷新页面

加载更多

关于ThinkPHP5.1+的Log无法记录SQL调试记录的小经历

项目开发阶段,除了基本编码外,性能也需要实时关注与优化。之前我的大部分项目都是使用ThinkPHP5.0以及ThinkPHP3.2,对于框架提供的日志记录和日志配置都差不多,然后使用ThinkPHP5.1的时候...

北桥苏
30分钟前
1
0
TiDB Binlog 源码阅读系列文章(四)Pump server 介绍

作者: satoru 在 上篇文章 中,我们介绍了 TiDB 如何通过 Pump client 将 binlog 发往 Pump,本文将继续介绍 Pump server 的实现,对应的源码主要集中在 TiDB Binlog 仓库的 pump/server.go...

TiDB
33分钟前
0
0
OSChina 周五乱弹 ——不知道假装开心,装的像么

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @巴拉迪维 :天黑了 你很忧愁, 你说世界上, 找不到四块五的妞, 行走在凌晨两点的马路上, 你疲倦地拿着半盒黄鹤楼。#今日歌曲推荐# 《四块...

小小编辑
今天
2.5K
19
Windows下学习C语言有哪些集成开发软件?

前言 初学者学习C语言遇到的最大困难想必就是搭建环境了,相当多的初学者就是被搭建环境导致放弃了学习编程,就我自己的经验而言,初学编程不应该受限于环境,使用成熟好用的环境就可以了,之...

Allen5G
昨天
3
0
Hello,Servlet!

Servlet来源 上文说过了servlet是什么,我们从servlet是什么中也可以了解到servlet的来源:servlet是Java的一个类,并且能够运行在web容器上,所以servlet是按照web容器的规范和Java的规范写...

蒙尘
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部