# AP 數組中存在的最小解排列（算術級數） > 原文： [https://www.geeksforgeeks.org/minimum-de-arrangements-present-array-ap-arithmetic-progression/](https://www.geeksforgeeks.org/minimum-de-arrangements-present-array-ap-arithmetic-progression/) 給定一個 n 元素數組。 給定數組是某些算術級數的置換。 找到該數組中存在的最小解排列數，以使該數組成為算術級數。 **示例**： ``` Input : arr[] = [8, 6, 10 ,4, 2] Output : Minimum De-arrangement = 3 Explanation : arr[] = [10, 8, 6, 4, 2] is permutation which forms an AP and has minimum de-arrangements. Input : arr[] = [5, 10, 15, 25, 20] Output : Minimum De-arrangement = 2 Explanation : arr[] = [5, 10, 15, 20, 25] is permutation which forms an AP and has minimum de-arrangements. ``` 根據算術級數的性質，我們的序列將以遞增或遞減的方式排列。 同樣，我們知道，任何算術級數的倒數也將形成另一個算術級數。 因此，我們創建了一個原始數組的副本，然后按升序對給定的數組進行排序，然后再次找到不匹配的總數，之后我們將反轉排序后的數組并找到新的不匹配數。 比較兩個不匹配的計數，我們可以找到最小的失序數。 時間復雜度= O（nlogn）。 ## C++ ```cpp // CPP for counting minimum de-arrangements present // in an array. #include<bits/stdc++.h> using namespace std; // function to count Dearrangement int countDe (int arr[], int n) { ????// create a copy of original array ????vector <int> v (arr, arr+n); ????// sort the array ????sort(arr, arr+n); ????// traverse sorted array for counting mismatches ????int count1 = 0; ????for (int i=0; i<n; i++)??? ????????if (arr[i] != v[i]) ????????????count1++;???????? ????// reverse the sorted array ????reverse(arr,arr+n);???? ????// traverse reverse sorted array for counting? ????// mismatches ????int count2 = 0; ????for (int i=0; i<n; i++) ????????if (arr[i] != v[i])??????? ????????????count2++; ????// return minimum mismatch count ????return (min (count1, count2)); } // driver program int main() { ????int arr[] = {5, 9, 21, 17, 13}; ????int n = sizeof(arr)/sizeof(arr[0]); ????cout << "Minimum Dearrangement = " << countDe(arr, n); ????return 0; }? ``` ## Java ```java // Java code for counting minimum? // de-arrangements present in an array. import java.util.*; import java.lang.*; import java.util.Arrays; public class GeeksforGeeks{ ????// function to count Dearrangement ????public static int countDe(int arr[], int n){ ????????int v[] = new int[n]; ????????// create a copy of original array ????????for(int i = 0; i < n; i++) ????????????v[i] = arr[i];? ????????// sort the array ????????Arrays.sort(arr); ????????// traverse sorted array for? ????????// counting mismatches ????????int count1 = 0; ????????for (int i = 0; i < n; i++)? ????????????if (arr[i] != v[i]) ????????????count1++;????? ????????// reverse the sorted array ????????Collections.reverse(Arrays.asList(arr)); ????????// traverse reverse sorted array? ????????// for counting mismatches ????????int count2 = 0; ????????for (int i = 0; i < n; i++) ????????????if (arr[i] != v[i])????? ????????????????count2++; ????????// return minimum mismatch count ????????return (Math.min (count1, count2)); ????} ????// driver code ????public static void main(String argc[]){ ????????int arr[] = {5, 9, 21, 17, 13}; ????????int n = 5; ????????System.out.println("Minimum Dearrangement = "+ ????????????????????????????countDe(arr, n)); ????} } /*This code is contributed by Sagar Shukla.*/ ``` ## Python3 ```py # Python3 code for counting minimum? # de-arrangements present in an array. # function to count Dearrangement def countDe(arr, n): ????????i = 0 ????????# create a copy of? ????????# original array ????????v = arr.copy() ????????# sort the array ????????arr.sort() ????????# traverse sorted array for? ????????# counting mismatches ????????count1 = 0 ????????i = 0 ????????while( i < n ):? ????????????if (arr[i] != v[i]): ????????????????count1 = count1 + 1 ????????????i = i + 1 ????????# reverse the sorted array ????????arr.sort(reverse=True) ????????# traverse reverse sorted array? ????????# for counting mismatches ????????count2 = 0 ????????i = 0 ????????while( i < n ): ????????????if (arr[i] != v[i]):????? ????????????????count2 = count2 + 1 ????????????i = i + 1 ????????# return minimum mismatch count ????????return (min (count1, count2)) # Driven code arr = [5, 9, 21, 17, 13] n = 5 print ("Minimum Dearrangement =",countDe(arr, n)) # This code is contributed by "rishabh_jain". ``` ## C# ```cs // C# code for counting? // minimum de-arrangements? // present in an array. using System; class GFG { // function to count // Dearrangement public static int countDe(int[] arr,? ??????????????????????????int n) { ????int[] v = new int[n]; ????// create a copy ????// of original array ????for(int i = 0; i < n; i++) ????????v[i] = arr[i];? ????// sort the array ????Array.Sort(arr); ????// traverse sorted array for? ????// counting mismatches ????int count1 = 0; ????for (int i = 0; i < n; i++)? ????????if (arr[i] != v[i]) ????????count1++;? ????// reverse the sorted array ????Array.Reverse(arr); ????// traverse reverse sorted array? ????// for counting mismatches ????int count2 = 0; ????for (int i = 0; i < n; i++) ????????if (arr[i] != v[i])? ????????????count2++; ????// return minimum? ????// mismatch count ????return (Math.Min (count1, count2)); } // Driver code public static void Main() { ????int[] arr = new int[]{5, 9, 21, 17, 13}; ????int n = 5; ????Console.WriteLine("Minimum Dearrangement = " +? ?????????????????????????????????countDe(arr, n)); } } // This code is contributed by mits ``` ## PHP ```php <?php // PHP for counting minimum de-arrangements? // present in an array. // function to count Dearrangement function countDe ($arr, $n) { ????// create a copy of original array ????$v = $arr; ????// sort the array ????sort($arr); ????// traverse sorted array for? ????// counting mismatches ????$count1 = 0; ????for ($i = 0; $i < $n; $i++)? ????????if ($arr[$i] != $v[$i]) ????????????$count1++;? ????// reverse the sorted array ????rsort($arr);? ????// traverse reverse sorted array? ????// for counting mismatches ????$count2 = 0; ????for ($i = 0; $i < $n; $i++) ????????if ($arr[$i] != $v[$i])? ????????????$count2++; ????// return minimum mismatch count ????return (min($count1, $count2)); } // Driver Code $arr = array(5, 9, 21, 17, 13); $n = count($arr); echo "Minimum Dearrangement = " .? ???????????????countDe($arr, $n); // This code is contributed by mits ?> ``` **輸出**： ``` Minimum Dearrangement = 2 ``` * * * * * *