给定一个大小为n的未排序数组arr[0..n-1]，找到最小长度的子数组arr[s..e]，这样对该子数组进行排序就可以对整个数组进行排序。 例如： 1） 如果输入数组是[10,12,20,30,25,40,32,31,35,50,60]，那么程序应该能够发现子数组位于索引3和索引8之间。 2） 如果输入数组是[0,1,15,25,6,7,30,40,50]，那么程序应该能够发现子数组位于索引2和索引5之间。
null
解决方案： 1） 找到未排序的候选子阵列 a） 从左到右扫描，找到第一个大于下一个元素的元素。允许 s 是这样一个元素的索引。在上面的示例1中， s 是3（指数为30）。 b） 从右到左扫描，找到第一个元素（从右到左的顺序中的第一个），它比下一个元素（从右到左的顺序中的下一个）小。允许 E 是这样一个元素的索引。在上面的示例1中，e是7（索引为31）。 2） 检查对未排序的候选子数组进行排序是否会使整个数组排序。如果没有，则在子阵列中包含更多元素。 a） 在中查找最小值和最大值 arr[s..e] .设最小值和最大值为 闵 和 最大值 . 闵 和 最大值 因为[30,25,40,32,31]分别是25和40。 b） 查找表中的第一个元素（如果有） arr[0..s-1] 这比 闵 改变 s 以索引此元素。在上面的例子1中没有这样的元素。 c） 查找中的最后一个元素（如果有） arr[e+1..n-1] 这比max小，改变 E 以索引此元素。在上面的示例1中，e更改为8（索引为35） 3） 印刷品 s 和 E . 实施：
C++
// C++ program to find the Minimum length Unsorted Subarray, // sorting which makes the complete array sorted #include<bits/stdc++.h> using namespace std; void printUnsorted( int arr[], int n) { int s = 0, e = n-1, i, max, min; // step 1(a) of above algo for (s = 0; s < n-1; s++) { if (arr[s] > arr[s+1]) break ; } if (s == n-1) { cout << "The complete array is sorted" ; return ; } // step 1(b) of above algo for (e = n - 1; e > 0; e--) { if (arr[e] < arr[e-1]) break ; } // step 2(a) of above algo max = arr[s]; min = arr[s]; for (i = s + 1; i <= e; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // step 2(b) of above algo for ( i = 0; i < s; i++) { if (arr[i] > min) { s = i; break ; } } // step 2(c) of above algo for ( i = n -1; i >= e+1; i--) { if (arr[i] < max) { e = i; break ; } } // step 3 of above algo cout << "The unsorted subarray which" << " makes the given array" << endl << "sorted lies between the indices " << s << " and " << e; return ; } int main() { int arr[] = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printUnsorted(arr, arr_size); getchar (); return 0; } // This code is contributed // by Akanksha Rai |
C
// C program to find the Minimum length Unsorted Subarray, // sorting which makes the complete array sorted #include<stdio.h> void printUnsorted( int arr[], int n) { int s = 0, e = n-1, i, max, min; // step 1(a) of above algo for (s = 0; s < n-1; s++) { if (arr[s] > arr[s+1]) break ; } if (s == n-1) { printf ( "The complete array is sorted" ); return ; } // step 1(b) of above algo for (e = n - 1; e > 0; e--) { if (arr[e] < arr[e-1]) break ; } // step 2(a) of above algo max = arr[s]; min = arr[s]; for (i = s + 1; i <= e; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // step 2(b) of above algo for ( i = 0; i < s; i++) { if (arr[i] > min) { s = i; break ; } } // step 2(c) of above algo for ( i = n -1; i >= e+1; i--) { if (arr[i] < max) { e = i; break ; } } // step 3 of above algo printf ( " The unsorted subarray which makes the given array " " sorted lies between the indees %d and %d" , s, e); return ; } int main() { int arr[] = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}; int arr_size = sizeof (arr)/ sizeof (arr[0]); printUnsorted(arr, arr_size); getchar (); return 0; } |
JAVA
// Java program to find the Minimum length Unsorted Subarray, // sorting which makes the complete array sorted class Main { static void printUnsorted( int arr[], int n) { int s = 0 , e = n- 1 , i, max, min; // step 1(a) of above algo for (s = 0 ; s < n- 1 ; s++) { if (arr[s] > arr[s+ 1 ]) break ; } if (s == n- 1 ) { System.out.println( "The complete array is sorted" ); return ; } // step 1(b) of above algo for (e = n - 1 ; e > 0 ; e--) { if (arr[e] < arr[e- 1 ]) break ; } // step 2(a) of above algo max = arr[s]; min = arr[s]; for (i = s + 1 ; i <= e; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // step 2(b) of above algo for ( i = 0 ; i < s; i++) { if (arr[i] > min) { s = i; break ; } } // step 2(c) of above algo for ( i = n - 1 ; i >= e+ 1 ; i--) { if (arr[i] < max) { e = i; break ; } } // step 3 of above algo System.out.println( " The unsorted subarray which" + " makes the given array sorted lies" + " between the indices " +s+ " and " +e); return ; } public static void main(String args[]) { int arr[] = { 10 , 12 , 20 , 30 , 25 , 40 , 32 , 31 , 35 , 50 , 60 }; int arr_size = arr.length; printUnsorted(arr, arr_size); } } |
Python3
# Python3 program to find the Minimum length Unsorted Subarray, # sorting which makes the complete array sorted def printUnsorted(arr, n): e = n - 1 # step 1(a) of above algo for s in range ( 0 ,n - 1 ): if arr[s] > arr[s + 1 ]: break if s = = n - 1 : print ( "The complete array is sorted" ) exit() # step 1(b) of above algo e = n - 1 while e > 0 : if arr[e] < arr[e - 1 ]: break e - = 1 # step 2(a) of above algo max = arr[s] min = arr[s] for i in range (s + 1 ,e + 1 ): if arr[i] > max : max = arr[i] if arr[i] < min : min = arr[i] # step 2(b) of above algo for i in range (s): if arr[i] > min : s = i break # step 2(c) of above algo i = n - 1 while i > = e + 1 : if arr[i] < max : e = i break i - = 1 # step 3 of above algo print ( "The unsorted subarray which makes the given array" ) print ( "sorted lies between the indexes %d and %d" % ( s, e)) arr = [ 10 , 12 , 20 , 30 , 25 , 40 , 32 , 31 , 35 , 50 , 60 ] arr_size = len (arr) printUnsorted(arr, arr_size) # This code is contributed by Shreyanshi Arun |
C#
// C# program to find the Minimum length Unsorted Subarray, // sorting which makes the complete array sorted using System; class GFG { static void printUnsorted( int []arr, int n) { int s = 0, e = n-1, i, max, min; // step 1(a) of above algo for (s = 0; s < n-1; s++) { if (arr[s] > arr[s+1]) break ; } if (s == n-1) { Console.Write( "The complete " + "array is sorted" ); return ; } // step 1(b) of above algo for (e = n - 1; e > 0; e--) { if (arr[e] < arr[e-1]) break ; } // step 2(a) of above algo max = arr[s]; min = arr[s]; for (i = s + 1; i <= e; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // step 2(b) of above algo for ( i = 0; i < s; i++) { if (arr[i] > min) { s = i; break ; } } // step 2(c) of above algo for ( i = n -1; i >= e+1; i--) { if (arr[i] < max) { e = i; break ; } } // step 3 of above algo Console.Write( " The unsorted subarray which" + " makes the given array sorted lies " + " between the indices " +s+ " and " +e); return ; } public static void Main() { int []arr = {10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60}; int arr_size = arr.Length; printUnsorted(arr, arr_size); } } // This code contributed by Sam007 |
PHP
<?php // PHP program to find the Minimum length Unsorted Subarray, // sorting which makes the complete array sorted function printUnsorted(& $arr , $n ) { $s = 0; $e = $n - 1; // step 1(a) of above algo for ( $s = 0; $s < $n - 1; $s ++) { if ( $arr [ $s ] > $arr [ $s + 1]) break ; } if ( $s == $n - 1) { echo "The complete array is sorted" ; return ; } // step 1(b) of above algo for ( $e = $n - 1; $e > 0; $e --) { if ( $arr [ $e ] < $arr [ $e - 1]) break ; } // step 2(a) of above algo $max = $arr [ $s ]; $min = $arr [ $s ]; for ( $i = $s + 1; $i <= $e ; $i ++) { if ( $arr [ $i ] > $max ) $max = $arr [ $i ]; if ( $arr [ $i ] < $min ) $min = $arr [ $i ]; } // step 2(b) of above algo for ( $i = 0; $i < $s ; $i ++) { if ( $arr [ $i ] > $min ) { $s = $i ; break ; } } // step 2(c) of above algo for ( $i = $n - 1; $i >= $e + 1; $i --) { if ( $arr [ $i ] < $max ) { $e = $i ; break ; } } // step 3 of above algo echo " The unsorted subarray which makes " . "the given array " . "" . " sorted lies between the indees " . $s . " and " . $e ; return ; } // Driver code $arr = array (10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60); $arr_size = sizeof( $arr ); printUnsorted( $arr , $arr_size ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // Javascript program to find the Minimum length Unsorted Subarray, // sorting which makes the complete array sorted function printUnsorted(arr,n) { let s = 0, e = n-1, i, max, min; // step 1(a) of above algo for (s = 0; s < n-1; s++) { if (arr[s] > arr[s+1]) break ; } if (s == n-1) { document.write( "The complete array is sorted" ); return ; } // step 1(b) of above algo for (e = n - 1; e > 0; e--) { if (arr[e] < arr[e-1]) break ; } // step 2(a) of above algo max = arr[s]; min = arr[s]; for (i = s + 1; i <= e; i++) { if (arr[i] > max) max = arr[i]; if (arr[i] < min) min = arr[i]; } // step 2(b) of above algo for ( i = 0; i < s; i++) { if (arr[i] > min) { s = i; break ; } } // step 2(c) of above algo for ( i = n -1; i >= e+1; i--) { if (arr[i] < max) { e = i; break ; } } // step 3 of above algo document.write( " The unsorted subarray which" + " makes the given array sorted lies" + " between the indees " +s+ " and " +e); return ; } let arr=[10, 12, 20, 30, 25, 40, 32, 31, 35, 50, 60]; let arr_size = arr.length; printUnsorted(arr, arr_size); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
The unsorted subarray which makes the given array sorted lies between the indees 3 and 8
时间复杂性： O（n）
如果您发现上述代码/算法不正确，请写评论，或者找到更好的方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
