热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

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<=iarray[i],可以断言,如果这样的i存在多个,则原数组无法通过修改至多一个数变为非下降数组。那么是否满足这个条件的数组都可以通过修改一个数而满足非下降呢?不是的,比如[2,4,1,3],只有相邻的4,1不满足非下降,但它不能通过只改变一个数变为非下降。其实,如果只存在一个i满足array[i-1]>array[i],那么要修改的那个数一定在array[i-1]和array[i]这两个数之中,那么就可以套用上一种做法,对于两种情况分别进行判断即可。更进一步地来说,由于只有对于i才有array[i-1]>array[i]成立,所以别的所有相邻的数均满足非下降的条件,因此对于array[i-1]来说,它之前和它之后的数组均分别满足非下降的条件,对于array[i]亦是如此,所以,只需判断前后两段数组能否可以接成非下降的数组即可。具体来说,如果要修改的数是array[i-1],那么只需判断array[i-2]<=array[i]是否成立,同样的如果要修改array[i],那么应判断array[i-1]<=array[i+1]是否成立,当然如果array[i-1]或array[i]位于边界则直接成立。总结该算法:统计所有不满足非下降的相邻位置的个数count,如果count为0,则返回true(不用修改),若count大于1,则返回false,否则应进行进一步的判断:设不满足非下降的位置为i,array[i-1]>array[i],则最终返回true的条件为array[i-1]、array[i]为边界或者array[i-2]<=array[i]或者array[i-1]<=array[i+1]。时间复杂度为O(n),额外空间复杂度为O(1)。

参考程序

Java版本:

java怎么实现非下降数组

以上就是“java怎么实现非下降数组”这篇文章的所有内容,感谢各位的阅读!相信大家阅读完这篇文章都有很大的收获,小编每天都会为大家更新不同的知识,如果还想学习更多的知识,请关注编程笔记行业资讯频道。


推荐阅读
  • 优化ListView性能
    本文深入探讨了如何通过多种技术手段优化ListView的性能,包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]
  • 1:有如下一段程序:packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]
  • C++实现经典排序算法
    本文详细介绍了七种经典的排序算法及其性能分析。每种算法的平均、最坏和最好情况的时间复杂度、辅助空间需求以及稳定性都被列出,帮助读者全面了解这些排序方法的特点。 ... [详细]
  • 本文详细探讨了Java中的24种设计模式及其应用,并介绍了七大面向对象设计原则。通过创建型、结构型和行为型模式的分类,帮助开发者更好地理解和应用这些模式,提升代码质量和可维护性。 ... [详细]
  • 深入理解C++中的KMP算法:高效字符串匹配的利器
    本文详细介绍C++中实现KMP算法的方法,探讨其在字符串匹配问题上的优势。通过对比暴力匹配(BF)算法,展示KMP算法如何利用前缀表优化匹配过程,显著提升效率。 ... [详细]
  • 本文详细介绍了Java编程语言中的核心概念和常见面试问题,包括集合类、数据结构、线程处理、Java虚拟机(JVM)、HTTP协议以及Git操作等方面的内容。通过深入分析每个主题,帮助读者更好地理解Java的关键特性和最佳实践。 ... [详细]
  • 在金融和会计领域,准确无误地填写票据和结算凭证至关重要。这些文件不仅是支付结算和现金收付的重要依据,还直接关系到交易的安全性和准确性。本文介绍了一种使用C语言实现小写金额转换为大写金额的方法,确保数据的标准化和规范化。 ... [详细]
  • 在给定的数组中,除了一个数字外,其他所有数字都是相同的。任务是找到这个唯一的不同数字。例如,findUniq([1, 1, 1, 2, 1, 1]) 返回 2,findUniq([0, 0, 0.55, 0, 0]) 返回 0.55。 ... [详细]
  • 深入解析JVM垃圾收集器
    本文基于《深入理解Java虚拟机:JVM高级特性与最佳实践》第二版,详细探讨了JVM中不同类型的垃圾收集器及其工作原理。通过介绍各种垃圾收集器的特性和应用场景,帮助读者更好地理解和优化JVM内存管理。 ... [详细]
  • LeetCode 540:有序数组中的唯一元素
    来源:力扣(LeetCode),链接:https://leetcode-cn.com/problems/single-element-in-a-sorted-array。题目要求在仅包含整数的有序数组中,找到唯一出现一次的元素,并确保算法的时间复杂度为 O(log n) 和空间复杂度为 O(1)。 ... [详细]
  • PHP 编程疑难解析与知识点汇总
    本文详细解答了 PHP 编程中的常见问题,并提供了丰富的代码示例和解决方案,帮助开发者更好地理解和应用 PHP 知识。 ... [详细]
  • Yii 实现阿里云短信发送 ... [详细]
  • 本文详细介绍了Akka中的BackoffSupervisor机制,探讨其在处理持久化失败和Actor重启时的应用。通过具体示例,展示了如何配置和使用BackoffSupervisor以实现更细粒度的异常处理。 ... [详细]
  • Java内存管理与优化:自动与手动释放策略
    本文深入探讨了Java中的内存管理机制,包括自动垃圾回收和手动释放内存的方法。通过理解这些机制,开发者可以更好地优化程序性能并避免内存泄漏。 ... [详细]
  • 探讨一个显示数字的故障计算器,它支持两种操作:将当前数字乘以2或减去1。本文将详细介绍如何用最少的操作次数将初始值X转换为目标值Y。 ... [详细]
author-avatar
白人冰娟
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有