Dada una array permutada de longitud N de los primeros N números naturales, debemos indicar el número mínimo de intercambios requeridos en la array ordenada de los primeros N números naturales para alcanzar la array permutada dada donde un número se puede intercambiar con un máximo de 2 posiciones restantes para eso. Si no es posible alcanzar la array permutada mediante la condición de intercambio anterior, entonces no es posible imprimir.
Ejemplos:
Input : arr = [1, 2, 5, 3, 4] Output : 2 We 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 Possible It is not possible to reach above array just by swapping numbers 2 positions left to it.
Podemos resolver este problema usando inversiones . Como podemos ver, si un número está en una posición que está a más de 2 lugares de su posición real, entonces no es posible llegar allí simplemente intercambiando elementos en 2 posiciones a la izquierda y si todos los elementos satisfacen esta propiedad (hay <= 2 elementos más pequeños que el de la derecha), entonces la respuesta será simplemente un número total de inversiones en la array porque se necesitarán muchos intercambios para transformar la array en una array permutada.
Podemos encontrar el número de inversiones en N log N tiempo utilizando la técnica de ordenación por combinación que se explica aquí , por lo que la complejidad de tiempo total de la solución será O (N log N) únicamente.
Implementación:
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 function 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\n";
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 function 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\n" : 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 function 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 function 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 function 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\n" : res);
</script>
Producción
2
Complejidad de tiempo: O(N*logN)Espacio auxiliar: O(logN)
Este artículo es una contribución de Utkarsh Trivedi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA