java怎么实现非下降数组
今天小编给大家分享一下java怎么实现非下降数组的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。
站在用户的角度思考问题,与客户深入沟通,找到井冈山网站设计与井冈山网站推广的解决方案,凭借多年的经验,让设计与互联网技术结合,创造个性化、用户体验好的作品,建站类型包括:成都做网站、网站设计、企业官网、英文网站、手机端网站、网站推广、空间域名、网站空间、企业邮箱。业务覆盖井冈山地区。
给出包含n个整数的数组,你的任务是检查它是否可以通过修改至多一个元素变成非下降的。一个非下降的数组array对于所有的i(1<=i 样例1: ⅰ 输入: [4,2,3] ⅱ 输出: True ⅲ 说明: 可以把第一个数4修改为1,得到[1,2,3]为非下降的数组 样例2: ⅰ 输入: [4,2,1] ⅱ 输出: False ⅲ 说明: 无法通过修改至多一个元素使数组变为非下降的。 a.简单的思考可以得到,情况无非为三种:不需要修改就满足条件的、修改一个元素可满足条件的和修改一个元素也无法满足条件的。对于第一种情况,只需遍历数组看是否满足数组的每一项都大于等于前一项,满足则返回true。对于第二种情况,可以枚举要修改的那个数array[i],再去检查array[i]之前的数是否是非下降的,array[i]之后的数是否是非下降的,最后还应该检查array[i-1]<=array[i+1]是否成立(如果array[i]位于边界则无需检查),如果成立则可以将array[i]改为array[i-1]和array[i+1]之间的任何数使数组变为非下降数组,这是情况二,返回true,如果对于所有的i都不成立,则为情况三,返回false。这样做的时间复杂度为O(n^2),额外空间复杂度为O(1)。 b.修改一个数以后可以变成非下降的数组满足什么条件呢?显然,这样的数组应当满足只存在一对相邻的数不满足非下降的条件,即只存在唯一的i(1<=i Java版本:
以上就是“java怎么实现非下降数组”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注创新互联行业资讯频道。
网站栏目:java怎么实现非下降数组
网页URL:http://myzitong.com/article/gdssed.html