专栏首页Android先生面试常见算法——连续子序列问题

面试常见算法——连续子序列问题

新的一周,又到了上班的日子了,由于新型肺炎病毒还在持续,有些人可能收到通知还是在家里远程办公,但是有些人可能公司就要求回去公司上班了,在这里还是要提醒大家,无论是在家也好,在公司也好都要做好防护工作。

好了回到正题,不知道大家面试的时候有没有遇到过这种问题,“最长子序列”,“最多子序列”,“连续子序列”等问题,最近刷题的时候刷到一道挺有意思的题:

题目描述

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

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

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

本文分享自微信公众号 - IT先森养成记(cyg_24kshign),作者:24K纯帅豆

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-02-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 每日算法题——两数之和

    许久不见,终于开始在公司上班了,有一点不好的就是一整天都要戴着口罩,闷得慌,不知道大伙儿有没有这种感觉。

    用户2802329
  • Android编译时注解,和重复代码Say No!

    越来越多的Android框架都使用了注解来实现,如有名ButterKnife、Dagger2都是用编译时注解来生成代码,好处是比反射效率更高,稳定性、可读性也更...

    用户2802329
  • RecyclerView 梳理:点击&amp;长按事件、分割线、拖曳排序、滑动删除

    这次主要是把 RecyclerView 比较常用的基本的点,在这里集中整理一下。从这篇文章主要梳理以下几点:

    用户2802329
  • 【LeetCode】55. 跳跃游戏

    输入: [2,3,1,1,4] 输出: true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。...

    韩旭051
  • Leetcode 45 Jump Game II

    Given an array of non-negative integers, you are initially positioned at the fi...

    triplebee
  • Longest Consecutive Sequence

    Given an unsorted array of integers, find the length of the longest consecutive ...

    Tyan
  • 那些年我们一起学过的 Elasticsearch

    最开始听到这个单词(后面简称:ES)是在大三的一个午休时间,在某个技术灌水群。据群友聊天内容讲到应用很广。于是下来开始在网上扒拉相关资料。那个时候国内资料貌似还...

    Jared.Tan
  • c语言身份证号码验证

    15位的身份证号转为18位即可按同样方法来验证(如 130321860311519 ,15位,需要补为 130321XX860311519X ,前两个X...

    特立独行的猫a
  • web开发框架Flask学习一

    py3study
  • 基于图卷积神经网络的城市轨道交通流量预测

    《Predicting Station-Level Short-Term Passenger Flow in a Citywide Metro Network ...

    深度学习与交通大数据

扫码关注云+社区

领取腾讯云代金券