当前位置：首页 > news >正文

【算法】【数组与矩阵模块】求数组中需要排序的最短子数组长度

news 2025/7/17 21:39:37

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题

给定数组arr，求arr中需要排序的最短子数组的长度是多少？
如：
arr = 1,2,3,2,35,8,9
结果为5，
{3,2,35,8,9} 子数组需要排序

解决方案

原问题：
1、申请4个变量，right表示需要移动位置的最右边元素、left表示需要移动位置的最左边元素、cur表示当前游标、min表示遍历到目前的最小值
2、从右往左遍历，如果遇到cur>min的情况，则right = cur
3、再从左往右遍历，如果遇到cur > max的情况，则left = cur
原则：只要需要移动位置的元素都属于需要排序的子数组内

代码编写

java语言版本

原问题：

/*** 二轮测试：需要排序的最短子数组长度* @param arr* @return*/public static int sortLenCp1(int[] arr) {if (arr == null || arr.length == 0) {return 0;}// 边界值，为遍历到目前，最值数int bound = 0;// 遍历到目前，在最值数另一边导致顺序乱序的最左边或者最右边的数int indexleft = -1, rightIndex = -1;int i = arr.length-1;bound = arr[arr.length-1];while (i >= 0) {if (arr[i] < bound) {// 最值更新bound = arr[i];}else if (arr[i] > bound){// 更新需要移动到i右边的最左边的数indexleft = i;}i--;}// 从左到右遍历i = 0;bound = arr[0];while (i < arr.length) {if (arr[i] > bound) {bound = arr[i];}else if (arr[i] < bound){rightIndex = i;}i++;}if (indexleft == -1 && rightIndex == -1){
//            整个数组都是有序的return 0;}else{return rightIndex - indexleft + 1;}}public static void main(String[] args) {System.out.println(sortLenCp1(new int[]{1,2,3,2,35,8,9}));}