檢查是否反轉子數組使數組排序 · GeeksForGeeks 中文系列教程

# 檢查是否反轉子數組使數組排序 > 原文： [https://www.geeksforgeeks.org/check-reversing-sub-array-make-array-sorted/](https://www.geeksforgeeks.org/check-reversing-sub-array-make-array-sorted/) 給定一個由 **n 個**整數組成的數組。任務是檢查反轉一個子數組是否使該數組排序。如果已對數組進行排序或通過對子數組進行排序后反轉該數組，則打印“是”，否則打印“否”。 **示例**： ``` Input : arr [] = {1, 2, 5, 4, 3} Output : Yes By reversing the subarray {5, 4, 3}, the array will be sorted. Input : arr [] = { 1, 2, 4, 5, 3 } Output : No ``` **方法 1（簡單：`O(n^2)`** 一個簡單的解決方案是逐個考慮每個子數組，嘗試反轉每個子數組，并檢查反轉子數組是否構成整體如果是，則返回 true；如果反轉任何子數組都不能使數組排序，則返回 false。 **方法 2（排序：O（nlogn））**：這個想法是將給定數組與排序數組進行比較。復制給定數組并將其排序。現在，找到與排序數組不匹配的第一個索引和最后一個索引。如果找不到這樣的索引，請打印“是”。否則檢查索引之間的元素是否按降序排列。下面是上述方法的實現： ## C++ ```cpp // C++ program to check whether reversing a // sub array make the array sorted or not #include<bits/stdc++.h> using namespace std; // Return true, if reversing the subarray will // sort the array, else return false. bool checkReverse(int arr[], int n) { ????// Copying the array. ????int temp[n]; ????for (int i = 0; i < n; i++) ????????temp[i] = arr[i]; ????// Sort the copied array. ????sort(temp, temp + n); ????// Finding the first mismatch. ????int front; ????for (front = 0; front < n; front++) ????????if (temp[front] != arr[front]) ????????????break; ????// Finding the last mismatch. ????int back; ????for (back = n - 1; back >= 0; back--) ????????if (temp[back] != arr[back]) ????????????break; ????// If whole array is sorted ????if (front >= back) ????????return true; ????// Checking subarray is decreasing or not. ????do ????{ ????????front++; ????????if (arr[front - 1] < arr[front]) ????????????return false; ????} while (front != back); ????return true; } // Driven Program int main() { ????int arr[] = { 1, 2, 5, 4, 3 }; ????int n = sizeof(arr)/sizeof(arr[0]); ????checkReverse(arr, n)? (cout << "Yes" << endl): ??????????????????????????(cout << "No" << endl); ????return 0; } ``` ## Java ```java // Java program to check whether reversing a? // sub array make the array sorted or not import java.util.Arrays; class GFG { // Return true, if reversing the subarray will? // sort the array, else return false.? ????static boolean checkReverse(int arr[], int n) { ????????// Copying the array.? ????????int temp[] = new int[n]; ????????for (int i = 0; i < n; i++) { ????????????temp[i] = arr[i]; ????????} ????????// Sort the copied array.? ????????Arrays.sort(temp); ????????// Finding the first mismatch.? ????????int front; ????????for (front = 0; front < n; front++) { ????????????if (temp[front] != arr[front]) { ????????????????break; ????????????} ????????} ????????// Finding the last mismatch.? ????????int back; ????????for (back = n - 1; back >= 0; back--) { ????????????if (temp[back] != arr[back]) { ????????????????break; ????????????} ????????} ????????// If whole array is sorted? ????????if (front >= back) { ????????????return true; ????????} ????????// Checking subarray is decreasing or not.? ????????do { ????????????front++; ????????????if (arr[front - 1] < arr[front]) { ????????????????return false; ????????????} ????????} while (front != back); ????????return true; ????} // Driven Program? ????public static void main(String[] args) { ????????int arr[] = {1, 2, 5, 4, 3}; ????????int n = arr.length; ????????if (checkReverse(arr, n)) { ????????????System.out.print("Yes"); ????????} else { ????????????System.out.print("No"); ????????} ????} } //This code contributed by 29AjayKumar? ``` ## Python3 ```py # Python3 program to check whether? # reversing a sub array make the # array sorted or not # Return true, if reversing the? # subarray will sort the array,? # else return false.? def checkReverse(arr, n): ????# Copying the array ????temp = [0] * n ????for i in range(n): ????????temp[i] = arr[i] ????# Sort the copied array.? ????temp.sort() ????# Finding the first mismatch.? ????for front in range(n): ????????if temp[front] != arr[front]: ????????????break ????# Finding the last mismatch.? ????for back in range(n - 1, -1, -1): ????????if temp[back] != arr[back]: ????????????break ????#If whole array is sorted ????if front >= back: ????????return True ????while front != back: ????????front += 1 ????????if arr[front - 1] < arr[front]: ????????????return False ????return True # Driver code arr = [1, 2, 5, 4, 3] n = len(arr) if checkReverse(arr, n) == True: ????print("Yes") else: ????print("No") # This code is contributed? # by Shrikant13 ``` ## C# ```cs // C# program to check whether reversing a? // sub array make the array sorted or not using System; class GFG { // Return true, if reversing the? // subarray will sort the array, // else return false.? static bool checkReverse(int []arr, int n)? { ????// Copying the array.? ????int []temp = new int[n]; ????for (int i = 0; i < n; i++)? ????{ ????????temp[i] = arr[i]; ????} ????// Sort the copied array.? ????Array.Sort(temp); ????// Finding the first mismatch.? ????int front; ????for (front = 0; front < n; front++) ????{ ????????if (temp[front] != arr[front]) ????????{ ????????????break; ????????} ????} ????// Finding the last mismatch.? ????int back; ????for (back = n - 1; back >= 0; back--)? ????{ ????????if (temp[back] != arr[back]) ????????{ ????????????break; ????????} ????} ????// If whole array is sorted? ????if (front >= back) ????{ ????????return true; ????} ????// Checking subarray is decreasing ????// or not.? ????do? ????{ ????????front++; ????????if (arr[front - 1] < arr[front]) ????????{ ????????????return false; ????????} ????} while (front != back); ????return true; } // Driven Program? public static void Main()? { ????int []arr = {1, 2, 5, 4, 3}; ????int n = arr.Length; ????if (checkReverse(arr, n))? ????{ ????????Console.Write("Yes"); ????}? ????else? ????{ ????????Console.Write("No"); ????} } } // This code is contributed // by PrinciRaj ``` ## PHP ```php <?php // PHP program to check whether reversing a // sub array make the array sorted or not // Return true, if reversing the subarray? // will sort the array, else return false. function checkReverse($arr, $n) { ????// Copying the array. ????$temp[$n] = array(); ????for ($i = 0; $i < $n; $i++) ????????$temp[$i] = $arr[$i]; ????// Sort the copied array. ????sort($temp, 0); ????// Finding the first mismatch. ????$front; ????for ($front = 0; $front < $n; $front++) ????????if ($temp[$front] != $arr[$front]) ????????????break; ????// Finding the last mismatch. ????$back; ????for ($back = $n - 1; $back >= 0; $back--) ????????if ($temp[$back] != $arr[$back]) ????????????break; ????// If whole array is sorted ????if ($front >= $back) ????????return true; ????// Checking subarray is decreasing or not. ????do ????{ ????????$front++; ????????if ($arr[$front - 1] < $arr[$front]) ????????????return false; ????} while ($front != $back); ????return true; } // Driver Code $arr = array( 1, 2, 5, 4, 3 ); $n = sizeof($arr); if(checkReverse($arr, $n)) ????echo "Yes" . "\n"; else ????echo "No" . "\n"; // This code is contributed // by Akanksha Rai ?> ``` **輸出**： ``` Yes ``` **時間復雜度**： O（nlogn）。 **方法 3（線性：`O(n)`）**：觀察到，對數組進行排序或數組由三部分組成時，答案為“是”。第一部分是增加子數組，然后減少子數組，然后再次增加子數組。因此，我們需要檢查數組包含遞增元素，然后包含遞減元素，然后遞增元素。在其他所有情況下，答案均為“否”。以下是此方法的實現： ## C++ ``` // C++ program to check whether reversing a sub array // make the array sorted or not #include<bits/stdc++.h> using namespace std; // Return true, if reversing the subarray will sort t // he array, else return false. bool checkReverse(int arr[], int n) { ????if (n == 1) ????????return true; ????// Find first increasing part ????int i; ????for (i=1; i < n && arr[i-1] < arr[i]; i++); ????if (i == n) ????????return true; ????// Find reversed part ????int j = i; ????while (j < n && arr[j] < arr[j-1]) ????{ ????????if (i > 1 && arr[j] < arr[i-2]) ????????????return false; ????????j++; ????} ????if (j == n) ????????return true; ????// Find last increasing part ????int k = j; ????// To handle cases like {1,2,3,4,20,9,16,17} ????if (arr[k] < arr[i-1]) ???????return false; ????while (k > 1 && k < n) ????{ ????????if (arr[k] < arr[k-1]) ????????????return false; ????????k++; ????} ????return true; } // Driven Program int main() { ????int arr[] = {1, 3, 4, 10, 9, 8}; ????int n = sizeof(arr)/sizeof(arr[0]); ????checkReverse(arr, n)? cout << "Yes" : cout << "No"; ????return 0; } ```