对高校网站建设的期待,设计用哪些网站有哪些功能,wordpress分类函数,wordpress播放视频播放器目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过#xff0c;但是不保证100%的测试用例#xff0c;如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识#xff01; 问题介绍 …
目录前言问题介绍解决方案代码编写java语言版本c语言版本c语言版本思考感悟写在最后前言
当前所有算法都使用测试用例运行过但是不保证100%的测试用例如果存在问题务必联系批评指正~ 在此感谢左大神让我对算法有了新的感悟认识 问题介绍
原问题
给定数组arr求arr中需要排序的最短子数组的长度是多少 如 arr 1,2,3,2,35,8,9 结果为5 {3,2,35,8,9} 子数组需要排序
解决方案
原问题 1、申请4个变量right表示需要移动位置的最右边元素、left表示需要移动位置的最左边元素、cur表示当前游标、min表示遍历到目前的最小值 2、从右往左遍历如果遇到curmin的情况则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}));}
c语言版本
正在学习中
c语言版本
正在学习中
思考感悟
这道题就表达了一个原则只要当前元素在排序中需要移动位置那么一定就在需要排序的子数组中。根据这个该算法就能够在On的时间内计算出子数组的长度以及子数组了。
写在最后 方案和代码仅提供学习和思考使用切勿随意滥用如有错误和不合理的地方务必批评指正~ 如果需要git源码可邮件给2260755767qq.com 再次感谢左大神对我算法的指点迷津
