给定前N个自然数的长度为N的置换数组，我们需要告诉前N个自然数的排序数组中所需的最小交换次数，以达到给定的置换数组，其中一个数最多可以交换2个位置。如果无法通过上述交换条件到达置换数组，则无法打印。
null
例如：
Input : arr = [1, 2, 5, 3, 4]Output : 2We can reach to above-permuted array in total 2 swaps as shown below,[1, 2, 3, 4, 5] -> [1, 2, 3, 5, 4] -> [1, 2, 5, 3, 4]Input : arr[] = [5, 1, 2, 3, 4]Output : Not PossibleIt is not possible to reach above array just by swapping numbers 2 positions leftto it.
我们可以使用 倒置 我们可以看到，如果一个数字位于一个距离其实际位置超过2个位置的位置，那么仅仅通过交换左2个位置的元素是不可能到达那里的，并且如果所有元素都满足这个属性（有<=2个元素小于它在右边），那么答案将只是数组中的反转总数，因为许多交换将被忽略需要将数组转换为置换数组。 使用合并排序技术，我们可以在N logn时间内找到反转数 在这里 所以解的总时间复杂度将仅为O（N logn）。
C++
// C++ program to find minimum number of swaps // to reach a permutation with at most 2 left // swaps allowed for every element #include <bits/stdc++.h> using namespace std; /* This funt merges two sorted arrays and returns inversion count in the arrays.*/ int merge( int arr[], int temp[], int left, int mid, int right) { int inv_count = 0; int i = left; /* i is index for left subarray*/ int j = mid; /* j is index for right subarray*/ int k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) temp[k++] = arr[i++]; /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) temp[k++] = arr[j++]; /*Copy back the merged elements to original array*/ for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ int _mergeSort( int arr[], int temp[], int left, int right) { int mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left)/2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid+1, right); /*Merge the two parts*/ inv_count += merge(arr, temp, left, mid+1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ int mergeSort( int arr[], int array_size) { int *temp = ( int *) malloc ( sizeof ( int )*array_size); return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of swaps to reach // permuted array 'arr' int minSwapToReachArr( int arr[], int N) { // loop over all elements to check Invalid // permutation condition for ( int i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) return -1; } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ int numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver code to test above methods int main() { // change below example int arr[] = {1, 2, 5, 3, 4}; int N = sizeof (arr) / sizeof ( int ); int res = minSwapToReachArr(arr, N); if (res == -1) cout << "Not Possible" ; else cout << res << endl; return 0; } |
JAVA
// Java program to find minimum // number of swaps to reach a // permutation with at most 2 left // swaps allowed for every element class GFG { /* This funt merges two sorted arrays and returns inversion count in the arrays.*/ static int merge( int arr[], int temp[], int left, int mid, int right) { int inv_count = 0 ; int i = left; /* i is index for left subarray*/ int j = mid; /* j is index for right subarray*/ int k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1 ) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1 ) { temp[k++] = arr[i++]; } /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) { temp[k++] = arr[j++]; } /* Copy back the merged elements to original array*/ for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ static int _mergeSort( int arr[], int temp[], int left, int right) { int mid, inv_count = 0 ; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left) / 2 ; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1 , right); /* Merge the two parts*/ inv_count += merge(arr, temp, left, mid + 1 , right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ static int mergeSort( int arr[], int array_size) { int [] temp = new int [array_size]; return _mergeSort(arr, temp, 0 , array_size - 1 ); } // method returns minimum number of // swaps to reach permuted array 'arr' static int minSwapToReachArr( int arr[], int N) { // loop over all elements to check Invalid // permutation condition for ( int i = 0 ; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1 ) - i > 2 ) { return - 1 ; } } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ int numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver code public static void main(String[] args) { // change below example int arr[] = { 1 , 2 , 5 , 3 , 4 }; int N = arr.length; int res = minSwapToReachArr(arr, N); System.out.println(res == - 1 ? "Not Possible" : res); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program to find minimum number of # swaps to reach a permutation with at most # 2 left swaps allowed for every element # This funt merges two sorted arrays and # returns inversion count in the arrays. def merge(arr, temp, left, mid, right): inv_count = 0 i = left # i is index for left subarray j = mid # j is index for right subarray k = left # k is index for resultant merged subarray while (i < = mid - 1 ) and (j < = right): if arr[i] < = arr[j]: temp[k] = arr[i] k, i = k + 1 , i + 1 else : temp[k] = arr[j] k, j = k + 1 , j + 1 inv_count = inv_count + (mid - i) # Copy the remaining elements of left # subarray (if there are any) to temp while i < = mid - 1 : temp[k] = arr[i] k, i = k + 1 , i + 1 # Copy the remaining elements of right # subarray (if there are any) to temp while j < = right: temp[k] = arr[j] k, j = k + 1 , j + 1 # Copy back the merged elements to original array for i in range (left, right + 1 ): arr[i] = temp[i] return inv_count # An auxiliary recursive function that # sorts the input array and returns the # number of inversions in the array. def _mergeSort(arr, temp, left, right): inv_count = 0 if right > left: # Divide the array into two parts # and call _mergeSortAndCountInv() # for each of the parts mid = (right + left) / / 2 # Inversion count will be sum of # inversions in left-part, right-part # and number of inversions in merging inv_count = _mergeSort(arr, temp, left, mid) inv_count + = _mergeSort(arr, temp, mid + 1 , right) # Merge the two parts inv_count + = merge(arr, temp, left, mid + 1 , right) return inv_count # This function sorts the input array and # returns the number of inversions in the array def mergeSort(arr, array_size): temp = [ None ] * array_size return _mergeSort(arr, temp, 0 , array_size - 1 ) # method returns minimum number of # swaps to reach permuted array 'arr' def minSwapToReachArr(arr, N): # loop over all elements to check # Invalid permutation condition for i in range ( 0 , N): # if an element is at distance more than 2 # from its actual position then it is not # possible to reach permuted array just # by swapping with 2 positions left elements # so returning -1 if (arr[i] - 1 ) - i > 2 : return - 1 # If permuted array is not Invalid, then number # of Inversion in array will be our final answer numOfInversion = mergeSort(arr, N) return numOfInversion # Driver code to test above methods if __name__ = = "__main__" : # change below example arr = [ 1 , 2 , 5 , 3 , 4 ] N = len (arr) res = minSwapToReachArr(arr, N) if res = = - 1 : print ( "Not Possible" ) else : print (res) # This code is contributed by Rituraj Jain |
C#
// C# program to find minimum // number of swaps to reach a // permutation with at most 2 left // swaps allowed for every element using System; class GFG { /* This funt merges two sorted arrays and returns inversion count in the arrays.*/ static int merge( int []arr, int []temp, int left, int mid, int right) { int inv_count = 0; int i = left; /* i is index for left subarray*/ int j = mid; /* j is index for right subarray*/ int k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) { temp[k++] = arr[i++]; } /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) { temp[k++] = arr[j++]; } /* Copy back the merged elements to original array*/ for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ static int _mergeSort( int []arr, int []temp, int left, int right) { int mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left) / 2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); /* Merge the two parts*/ inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ static int mergeSort( int []arr, int array_size) { int [] temp = new int [array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of // swaps to reach permuted array 'arr' static int minSwapToReachArr( int []arr, int N) { // loop over all elements to check Invalid // permutation condition for ( int i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) { return -1; } } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ int numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver code static void Main() { // change below example int []arr = {1, 2, 5, 3, 4}; int N = arr.Length; int res = minSwapToReachArr(arr, N); if (res == -1) Console.WriteLine( "Not Possible" ); else Console.WriteLine(res); } } // This code is contributed by mits |
Javascript
<script> // JavaScript program to find minimum // number of swaps to reach a // permutation with at most 2 left // swaps allowed for every element /* This funt merges two sorted arrays and returns inversion count in the arrays.*/ function merge(arr, temp, left, mid, right) { let inv_count = 0; let i = left; /* i is index for left subarray*/ let j = mid; /* j is index for right subarray*/ let k = left; /* k is index for resultant merged subarray*/ while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } /* Copy the remaining elements of left subarray (if there are any) to temp*/ while (i <= mid - 1) { temp[k++] = arr[i++]; } /* Copy the remaining elements of right subarray (if there are any) to temp*/ while (j <= right) { temp[k++] = arr[j++]; } /* Copy back the merged elements to original array*/ for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inv_count; } /* An auxiliary recursive function that sorts the input array and returns the number of inversions in the array. */ function _mergeSort(arr, temp, left, right) { let mid, inv_count = 0; if (right > left) { /* Divide the array into two parts and call _mergeSortAndCountInv() for each of the parts */ mid = (right + left) / 2; /* Inversion count will be sum of inversions in left-part, right-part and number of inversions in merging */ inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); /* Merge the two parts*/ inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } /* This function sorts the input array and returns the number of inversions in the array */ function mergeSort(arr, array_size) { let temp = Array.from({length: array_size}, (_, i) => 0); return _mergeSort(arr, temp, 0, array_size - 1); } // method returns minimum number of // swaps to reach permuted array 'arr' function minSwapToReachArr(arr, N) { // loop over all elements to check Invalid // permutation condition for (let i = 0; i < N; i++) { /* if an element is at distance more than 2 from its actual position then it is not possible to reach permuted array just by swapping with 2 positions left elements so returning -1 */ if ((arr[i] - 1) - i > 2) { return -1; } } /* If permuted array is not Invalid, then number of Inversion in array will be our final answer */ let numOfInversion = mergeSort(arr, N); return numOfInversion; } // Driver Code // change below example let arr = [1, 2, 5, 3, 4]; let N = arr.length; let res = minSwapToReachArr(arr, N); document.write(res == -1 ? "Not Possible" : res); </script> |
输出：
2
本文由 乌特卡什·特里维迪 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
