leetcode最短无序连续子数组
2021/8/3 23:10:12
本文主要是介绍leetcode最短无序连续子数组,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
平民解法:
既然是找最小数组,那就得到一个排序好的数组,然后直接和初试数组比对,用一个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)
这篇关于leetcode最短无序连续子数组的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享