leetcode最短无序连续子数组
2024-08-31 07:21:40
平民解法:
既然是找最小数组,那就得到一个排序好的数组,然后直接和初试数组比对,用一个left,right分别记录从最初开始不同,到最后不同的小标,最后左右做差再加一,就能得到长度。
其他解法:
双指针 + 线性扫描
另外一个做法是,我们把整个数组分成三段处理。
起始时,先通过双指针 ii 和 jj 找到左右两次侧满足 单调递增 的分割点。
即此时 [0, i][0,i] 和 [j, n)[j,n) 满足升序要求,而中间部分 (i, j)(i,j) 不确保有序。
然后我们对中间部分 [i, j][i,j] 进行遍历:
发现 nums[x] < nums[i - 1]nums[x]<nums[i−1]:由于对 [i, j][i,j] 部分进行排序后 nums[x]nums[x] 会出现在 nums[i - 1]nums[i−1] 后,将不满足整体升序,此时我们需要调整分割点 ii 的位置;
发现 nums[x] > nums[j + 1]nums[x]>nums[j+1]:由于对 [i, j][i,j] 部分进行排序后 nums[x]nums[x] 会出现在 nums[j + 1]nums[j+1] 前,将不满足整体升序,此时我们需要调整分割点 jj 的位置。
链接:https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/solution/gong-shui-san-xie-yi-ti-shuang-jie-shuan-e1le/
来源:力扣(LeetCode)
最新文章
- epoll ET模式陷阱分析
- label正确显示多行数据
- 简易版viewport
- route工具
- CentOS 5.x版本升级PHP
- .NET设计模式(19):观察者模式(Observer Pattern)(转)
- Oracle基础<;4>;--程序包
- iOS开发——数据持久化Swift篇&;模型对象归档
- MemCachedClient数据写入的三个方法
- Android4.3模拟器界面中右侧菜单按钮无法使用问题解决办法
- phabricator在mac上的搭建(转)
- SZU:B47 Big Integer I
- iOS完美版的UIScrollView无缝循环:你值得一看
- validateform正则表达式 datatype验证数字
- iOS中 Swift初级入门学习(三)
- 将本地jar包打包到本地仓库和上传到私服
- [转载] java多线程总结(三)
- BZOJ4482[Jsoi2015]套娃——贪心+set
- numpy学习之前的必要数学知识:线性代数
- 用户 &#39;IIS APPPOOL\xxxx&#39; 登录失败