Dados dos arreglos arr1[] y arr2[] de tamaño N cada uno, la tarea es encontrar el número mínimo de intercambio de los mismos elementos indexados necesarios para hacer que ambos arreglos sean estrictamente crecientes.
Nota: Devuelva -1 si no es posible hacerlos estrictamente crecientes.
Ejemplos:
Entrada: arr1 = {1, 3, 5, 4}, arr2 = {1, 2, 3, 7}
Salida: 1
Explicación:
Intercambiar arr1[3] y arr2[3].
Entonces las sucesiones son:
arr1 = [1, 3, 5, 7] y arr2 = [1, 2, 3, 4] ambas estrictamente crecientes.
Por lo tanto, número mínimo de intercambios requeridos = 1.Entrada: arr1 = {0, 3, 5, 8, 9}, nums2 = {2, 1, 4, 6, 9}
Salida: 1
Planteamiento: El problema se puede resolver con base en la siguiente observación:
Para cada índice hay dos opciones: intercambiar los elementos o no. Si en ambos casos los prefijos de ambas arrays no son estrictamente crecientes, entonces no es posible realizar la tarea. De lo contrario, continúe con este enfoque.
La observación anterior se puede implementar utilizando el concepto de programación dinámica . Cree dos arrays dp[] donde –
- El i -ésimo índice de uno almacenará los pasos mínimos requeridos para hacer que los prefijos aumenten estrictamente cuando los elementos actuales se intercambian y
- La otra array almacenará los pasos mínimos cuando la actual no se intercambie.
Siga los pasos mencionados a continuación para implementar la observación anterior:
- Considere dos arreglos swap[] y noswap[] donde –
- swap[i] almacena los pasos mínimos cuando arr1[i] y arr2[i] se intercambian dado que la array está ordenada de 0 a i-1 .
- noswap[i] almacena los pasos mínimos cuando no hay intercambio entre arr1[i] y arr2[i] dado que la array está ordenada de 0 a i-1 .
- Iterar la array y, en función de las relaciones entre los elementos de la array en el índice i – th y (i-1) th , actualizar el valor de las arrays.
- Si arr1[i] y arr2[i] son mayores que los (i-1) -ésimos elementos de ambas arrays, entonces
- Si se intercambian los valores actuales, también se debe intercambiar el anterior. Entonces intercambiar[i] = intercambiar[i-1]+1
- Si los elementos actuales no se intercambian, se debe hacer lo mismo con los elementos anteriores. Entonces, intercambio[i] = intercambio[i-1]
- Si arr1[i] es mayor que arr2[i-1] y arr2[i] mayor que arr1[i-1]:
- Si intercambiamos i -ésimos elementos del índice, entonces no deberíamos intercambiar (i-1) los elementos del índice. Entonces swap[i] = min(swap[i], noswap[i-1]).
- Debido a la misma condición noswap[i] = min(noswap[i], swap[i-1]+1).
- Si arr1[i] y arr2[i] son mayores que los (i-1) -ésimos elementos de ambas arrays, entonces
- La respuesta requerida es el mínimo entre los valores en el último índice de la array swap[] y la array noswap[] .
A continuación se muestra la implementación del enfoque mencionado anteriormente:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate
// the minimum swaps required or
// it is not possible
int minSwap(int A[], int B[], int n)
{
int swap[n], no_swap[n];
swap[0] = 1;
no_swap[0] = 0;
// Loop to implement the dynamic programming
for (int i = 1; i < n; ++i) {
swap[i] = no_swap[i] = n;
// assigning n to both of these
// so that they can be compared easily
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
// If we swap position i,
// we need to swap position i - 1.
swap[i] = swap[i - 1] + 1;
// If we don't swap position i,
// we should not swap position i - 1.
no_swap[i] = no_swap[i - 1];
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
// If we swap position i,
// we should not swap position i - 1.
swap[i] = min(swap[i],
no_swap[i - 1] + 1);
// If we don't swap position i,
// we should swap position i - 1.
no_swap[i] = min(no_swap[i],
swap[i - 1]);
}
// If any one the array is not possible
// to be made strictly increasing
if ((A[i] < A[i - 1] && A[i] < B[i - 1])
|| (B[i] < B[i - 1] && B[i] < A[i - 1])) {
return -1;
}
}
// Return the answer
return min(swap[n - 1], no_swap[n - 1]);
}
// Driver Code
int main()
{
int arr1[] = { 1, 3, 5, 4 };
int arr2[] = { 1, 2, 3, 7 };
int N = sizeof(arr1) / sizeof(arr1[0]);
// Function call
int ans = minSwap(arr1, arr2, N);
cout << ans << endl;
return 0;
}
Java
// Java program for above approach
import java.util.ArrayList;
class GFG {
// Function to calculate
// the minimum swaps required or
// it is not possible
static int minSwap(int A[], int B[], int n)
{
int swap[] = new int[n], no_swap[] = new int[n];
swap[0] = 1;
no_swap[0] = 0;
// Loop to implement the dynamic programming
for (int i = 1; i < n; ++i) {
swap[i] = no_swap[i] = n;
// assigning n to both of these
// so that they can be compared easily
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
// If we swap position i,
// we need to swap position i - 1.
swap[i] = swap[i - 1] + 1;
// If we don't swap position i,
// we should not swap position i - 1.
no_swap[i] = no_swap[i - 1];
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
// If we swap position i,
// we should not swap position i - 1.
swap[i] = Math.min(swap[i],
no_swap[i - 1] + 1);
// If we don't swap position i,
// we should swap position i - 1.
no_swap[i] = Math.min(no_swap[i],
swap[i - 1]);
}
// If any one the array is not possible
// to be made strictly increasing
if ((A[i] < A[i - 1] && A[i] < B[i - 1])
|| (B[i] < B[i - 1] && B[i] < A[i - 1])) {
return -1;
}
}
// Return the answer
return Math.min(swap[n - 1], no_swap[n - 1]);
}
// Driver code
public static void main(String args[]) {
int arr1[] = { 1, 3, 5, 4 };
int arr2[] = { 1, 2, 3, 7 };
int N = arr1.length;
// Function call
int ans = minSwap(arr1, arr2, N);
System.out.print(ans);
}
}
// This code is contributed by code_hunt.
Python3
# Python code to implement the approach # Function to calculate # the minimum swaps required or # it is not possible def minSwap(A, B, n): swap = [0] * n no_swap = [0] * n swap[0] = 1 no_swap[0] = 0 # Loop to implement the dynamic programming for i in range(1, n): swap[i] = no_swap[i] = n # assigning n to both of these # so that they can be compared easily if A[i] > A[i - 1] and B[i] > B[i - 1]: # If we swap position i, # we need to swap position i - 1. swap[i] = swap[i - 1] + 1 # If we don't swap position i, # we should not swap position i - 1. no_swap[i] = no_swap[i - 1] if A[i] > B[i - 1] and B[i] > A[i - 1]: # If we swap position i, # we should not swap position i - 1. swap[i] = min(swap[i], no_swap[i - 1] + 1) # If we don't swap position i, # we should swap position i - 1. no_swap[i] = min(no_swap[i], swap[i - 1]) # If any one the array is not possible # to be made strictly increasing if (A[i] < A[i - 1] and A[i] < B[i - 1]) or (B[i] < B[i - 1] and B[i] < A[i - 1]): return -1 # Return the answer return min(swap[n-1], no_swap[n-1]) # Driver Code if __name__ == '__main__': arr1 = [1, 3, 5, 4] arr2 = [1, 2, 3, 7] N = len(arr1) # Function call ans = minSwap(arr1, arr2, N) print(ans) # This code is contributed by Tapesh(tapeshdua420)
C#
// C# program for above approach
using System;
public class GFG {
// Function to calculate
// the minimum swaps required or
// it is not possible
static int minSwap(int []A, int []B, int n)
{
int []swap = new int[n];
int []no_swap = new int[n];
swap[0] = 1;
no_swap[0] = 0;
// Loop to implement the dynamic programming
for (int i = 1; i < n; ++i) {
swap[i] = no_swap[i] = n;
// assigning n to both of these
// so that they can be compared easily
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
// If we swap position i,
// we need to swap position i - 1.
swap[i] = swap[i - 1] + 1;
// If we don't swap position i,
// we should not swap position i - 1.
no_swap[i] = no_swap[i - 1];
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
// If we swap position i,
// we should not swap position i - 1.
swap[i] = Math.Min(swap[i], no_swap[i - 1] + 1);
// If we don't swap position i,
// we should swap position i - 1.
no_swap[i] = Math.Min(no_swap[i],swap[i - 1]);
}
// If any one the array is not possible
// to be made strictly increasing
if ((A[i] < A[i - 1] && A[i] < B[i - 1])|| (B[i] < B[i - 1] && B[i] < A[i - 1])) {
return -1;
}
}
// Return the answer
return Math.Min(swap[n - 1], no_swap[n - 1]);
}
// Driver code
static public void Main(string []args) {
int []arr1 = {1,3,5,4};
int []arr2 = {1,2,3,7};
int N = arr1.Length;
// Function call
int ans = minSwap(arr1, arr2, N);
Console.WriteLine(ans);
}
}
// This code is contributed by AnkThon
Javascript
<script>
// Javascript code to implement the approach
// Function to calculate
// the minimum swaps required or
// it is not possible
function minSwap(A,B,n)
{
let swap = [];
let no_swap = [];
swap[0] = 1;
no_swap[0] = 0;
// Loop to implement the dynamic programming
for (let i = 1; i < n; ++i) {
swap[i] = no_swap[i] = n;
// assigning n to both of these
// so that they can be compared easily
if (A[i] > A[i - 1] && B[i] > B[i - 1]) {
// If we swap position i,
// we need to swap position i - 1.
swap[i] = swap[i - 1] + 1;
// If we don't swap position i,
// we should not swap position i - 1.
no_swap[i] = no_swap[i - 1];
}
if (A[i] > B[i - 1] && B[i] > A[i - 1]) {
// If we swap position i,
// we should not swap position i - 1.
swap[i] = Math.min(swap[i],
no_swap[i - 1] + 1);
// If we don't swap position i,
// we should swap position i - 1.
no_swap[i] = Math.min(no_swap[i],
swap[i - 1]);
}
// If any one the array is not possible
// to be made strictly increasing
if ((A[i] < A[i - 1] && A[i] < B[i - 1])
|| (B[i] < B[i - 1] && B[i] < A[i - 1])) {
return -1;
}
}
// Return the answer
return Math.min(swap[n - 1], no_swap[n - 1]);
}
// Driver Code
let arr1 = [ 1, 3, 5, 4 ];
let arr2 = [ 1, 2, 3, 7 ];
let N = arr1.length;
// Function call
let ans = minSwap(arr1, arr2, N);
console.log(ans);
// This code is contributed by akashish__
</script>
Producción
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por apsingh123 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA