大橙子网站建设,新征程启航
为企业提供网站建设、域名注册、服务器等服务
这篇文章主要介绍“java如何实现非下降数组”,在日常操作中,相信很多人在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如何实现非下降数组
链接分享:http://dzwzjz.com/article/pdshpg.html