Dada una array desordenada de longitud n y un entero k, encuentre los intercambios mínimos para obtener la posición de k antes de usar la búsqueda binaria. Aquí podemos intercambiar dos números cualesquiera tantas veces como queramos. Si no podemos obtener la posición intercambiando elementos, imprima «-1».
Ejemplos:
Input : arr = {3, 10, 6, 7, 2, 5, 4}
k = 4
Output : 2
Explanation :
Here, after swapping 3 with 7 and 2 with 5, the
final array will look like {7, 10, 6, 3, 5, 2, 4}.
Now, if we provide this array to binary search we
can get the position of 4.
Input : arr = {3, 10, 6, 7, 2, 5, 4}
k = 10
Output : -1
Explanation :
Here, we can not get the position of 10 if we
provide this array to the binary search even
not with swapping some pairs.
Enfoque: antes de discutir el enfoque, debemos suponer que aquí no debemos intercambiar los pares. Solo necesitamos contar el número mínimo de intercambios para que, si proporcionamos la array recién creada a la búsqueda binaria, podamos obtener la posición de k. Para hacerlo, debemos pasar la array dada a la búsqueda binaria y centrarnos en las siguientes cosas:
- Antes de ir a la búsqueda binaria, necesitamos calcular el número de elementos mínimos, es decir, num_min de k, y el número de elementos máximos, es decir, num_max de k. Aquí, num_min denota la cantidad de elementos disponibles más pequeños de k y num_max denota la cantidad de elementos disponibles más grandes que podemos usar para intercambiar
- La posición real de k en la array dada.
Ahora, los siguientes son los casos de prueba que ocurrirán durante la implementación de la búsqueda binaria: –
Caso 1: Si arr[mid] es mayor que k, pero la posición de k es mayor que mid. La búsqueda binaria nos llevaría a (arr[0] a arr[mid-1]). Pero en realidad nuestro elemento está en el medio (arr[mid+1] a arr[último elemento]). Entonces, para ir en la dirección correcta, necesitamos algo más pequeño que k para poder intercambiarlo con arr[mid] y podemos ir entre arr[mid+1] y arr[last_element]. Entonces, aquí requerimos un intercambio, es decir , need_minimum .
Caso 2:Si arr[mid] es menor que k pero la posición de k es menor que mid. La búsqueda binaria nos llevaría a (arr[mid+1] a arr[last_element]). Pero en realidad nuestro elemento está en el medio (arr[0] a arr[mid-1]). Entonces, para ir en la dirección correcta, necesitamos algo mayor que k para que podamos intercambiarlo con arr[mid] y podamos ir entre arr[0] y arr[mid-1]. Entonces, aquí requerimos un intercambio, es decir , need_maximum .
Caso 3:
Si arr[mid] es mayor que k y la posición de k es menor que mid. Ahora, en este caso, la búsqueda binaria funcionaría bien. Pero espera, aquí está lo importante en lo que tenemos que trabajar. Como sabemos, en este caso, la búsqueda binaria funcionará bien, arr[mid] está en la posición correcta, por lo que no se usará en ningún intercambio, por lo que aquí tenemos que disminuir uno de sus mayores elementos disponibles, es decir, de num_max. Lo mismo ocurre con el caso en que arr[mid] es menor que k y la posición de k es mayor que mid. Aquí, tenemos que disminuir uno de sus elementos disponibles más pequeños, es decir, de num_min.
Caso 4: si arr[mid] == k o pos == mid entonces podemos salir fácilmente de la búsqueda binaria.
Entonces, hasta ahora hemos calculado el need_minimum, es decir, la cantidad mínima de elementos necesarios para el intercambio,need_maximum, es decir, el número máximo de elementos necesarios para el intercambio, num_max , es decir, el número total de elementos mayores de k que todavía están disponibles para el intercambio, y num_min , es decir, el número total de elementos mínimos de k que están disponibles para el intercambio.
Ahora aquí tenemos que considerar dos casos:
Caso 1:Si need_minimum es mayor que need_maximum. En este caso, tenemos que intercambiar todos estos elementos máximos necesarios con el menor de k. Entonces tenemos que usar los elementos más pequeños de num_min. Ahora todos los swaps de need_maximum están hechos. Aquí, lo principal es que cuando intercambiamos todos estos elementos máximos necesarios con elementos más pequeños, estos elementos más pequeños obtuvieron sus posiciones correctas. Entonces, indirectamente, hemos realizado algunos de los intercambios de elementos más pequeños necesarios y eso se calculará como need_minimum – need_maximum y también num_min disponible será num_min – need_maximum . Ahora, tenemos que calcular los intercambios necesarios_mínimos restantes. Podemos calcular estos intercambios si tenemos suficiente num_min, es decir, num_min > need_minimum. Para este caso, los swaps serán need_maximum + need_minimumde lo contrario será -1. El mismo concepto se aplica al caso cuando tenemos necesidad_mínima es menor que necesidad_máxima.
A continuación se muestra la implementación básica del enfoque anterior: –
C++
// CPP program to find Minimum number
// of swaps to get the position of
// the element if we provide an
// unsorted array to binary search.
#include <bits/stdc++.h>
using namespace std;
// Function to find minimum swaps.
int findMinimumSwaps(int* arr, int n,
int k)
{
int pos, num_min, num_max,
need_minimum, need_maximum, swaps;
num_min = num_max = need_minimum = 0;
need_maximum = swaps = 0;
// Here we are getting number of
// smaller and greater elements of k.
for (int i = 0; i < n; i++) {
if (arr[i] < k)
num_min++;
else if (arr[i] > k)
num_max++;
}
// Here we are calculating the actual
// position of k in the array.
for (int i = 0; i < n; i++) {
if (arr[i] == k) {
pos = i;
break;
}
}
int left, right, mid;
left = 0;
right = n - 1;
// Implementing binary search as
// per the above-discussed cases.
while (left <= right) {
mid = (left + right) / 2;
// If we find the k.
if (arr[mid] == k) {
break;
}
else if (arr[mid] > k) {
// If we need minimum
// element swap.
if (pos > mid)
need_minimum++;
else
// Else the element is
// at the right position.
num_min--;
left = mid + 1;
}
else {
if (pos < mid)
// If we need maximum
// element swap.
need_maximum++;
else
// Else element is at
// the right position
num_max--;
right = mid - 1;
}
}
// Calculating the required swaps.
if (need_minimum > need_maximum) {
swaps = swaps + need_maximum;
num_min = num_min - need_maximum;
need_minimum = need_minimum - need_maximum;
need_maximum = 0;
}
else {
swaps = swaps + need_minimum;
num_max = num_max - need_minimum;
need_maximum = need_maximum - need_minimum;
need_minimum = 0;
}
// If it is impossible.
if (need_maximum > num_max || need_minimum > num_min)
return -1;
else
return (swaps + need_maximum + need_minimum);
}
// Driver function
int main()
{
int arr[] = { 3, 10, 6, 7, 2, 5, 4 }, k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMinimumSwaps(arr, n, k);
}
Java
//Java program to find Minimum number
// of swaps to get the position of
// the element if we provide an
// unsorted array to binary search.
public class GFG {
// Function to find minimum swaps.
static int findMinimumSwaps(int[] arr, int n,
int k) {
int pos = 0, num_min, num_max,
need_minimum, need_maximum, swaps;
num_min = num_max = need_minimum = 0;
need_maximum = swaps = 0;
// Here we are getting number of
// smaller and greater elements of k.
for (int i = 0; i < n; i++) {
if (arr[i] < k) {
num_min++;
} else if (arr[i] > k) {
num_max++;
}
}
// Here we are calculating the actual
// position of k in the array.
for (int i = 0; i < n; i++) {
if (arr[i] == k) {
pos = i;
break;
}
}
int left, right, mid;
left = 0;
right = n - 1;
// Implementing binary search as
// per the above-discussed cases.
while (left <= right) {
mid = (left + right) / 2;
// If we find the k.
if (arr[mid] == k) {
break;
} else if (arr[mid] > k) {
// If we need minimum
// element swap.
if (pos > mid) {
need_minimum++;
} else // Else the element is
// at the right position.
{
num_min--;
}
left = mid + 1;
} else {
if (pos < mid) // If we need maximum
// element swap.
{
need_maximum++;
} else // Else element is at
// the right position
{
num_max--;
}
right = mid - 1;
}
}
// Calculating the required swaps.
if (need_minimum > need_maximum) {
swaps = swaps + need_maximum;
num_min = num_min - need_maximum;
need_minimum = need_minimum - need_maximum;
need_maximum = 0;
} else {
swaps = swaps + need_minimum;
num_max = num_max - need_minimum;
need_maximum = need_maximum - need_minimum;
need_minimum = 0;
}
// If it is impossible.
if (need_maximum > num_max || need_minimum > num_min) {
return -1;
} else {
return (swaps + need_maximum + need_minimum);
}
}
// Driver function
public static void main(String[] args) {
int arr[] = {3, 10, 6, 7, 2, 5, 4}, k = 4;
int n = arr.length;
System.out.println(findMinimumSwaps(arr, n, k));
}
}
/*This code is contributed by PrinciRaj1992*/
Python3
# Python3 program to find Minimum number # of swaps to get the position of # the element if we provide an # unsorted array to binary search. # Function to find minimum swaps. def findMinimumSwaps(arr, n, k): num_min = num_max = need_minimum = 0 need_maximum = swaps = 0 # Here we are getting number of # smaller and greater elements of k. for i in range(n): if (arr[i] < k): num_min += 1 elif (arr[i] > k): num_max += 1 # Here we are calculating the actual # position of k in the array. for i in range(n): if (arr[i] == k): pos = i break left = 0 right = n - 1 # Implementing binary search as # per the above-discussed cases. while (left <= right): mid = (left + right) // 2 # If we find the k. if (arr[mid] == k): break elif (arr[mid] > k): # If we need minimum # element swap. if (pos > mid): need_minimum += 1 else: # Else the element is # at the right position. num_min -= 1 left = mid + 1 else: if (pos < mid): # If we need maximum # element swap. need_maximum += 1 else: # Else element is at # the right position num_max -= 1 right = mid - 1 # Calculating the required swaps. if (need_minimum > need_maximum): swaps = swaps + need_maximum num_min = num_min - need_maximum need_minimum = (need_minimum - need_maximum) need_maximum = 0 else: swaps = swaps + need_minimum num_max = num_max - need_minimum need_maximum = (need_maximum - need_minimum) need_minimum = 0 # If it is impossible. if (need_maximum > num_max or need_minimum > num_min): return -1 else: return (swaps + need_maximum + need_minimum) # Driver function if __name__ == "__main__": arr = [3, 10, 6, 7, 2, 5, 4] k = 4 n = len(arr) print(findMinimumSwaps(arr, n, k)) # This code is contributed by Chitranayal
C#
// C# program to find Minimum number
// of swaps to get the position of
// the element if we provide an
// unsorted array to binary search.
using System;
public class GFG{
// Function to find minimum swaps.
static int findMinimumSwaps(int[] arr, int n,
int k) {
int pos = 0, num_min, num_max,
need_minimum, need_maximum, swaps;
num_min = num_max = need_minimum = 0;
need_maximum = swaps = 0;
// Here we are getting number of
// smaller and greater elements of k.
for (int i = 0; i < n; i++) {
if (arr[i] < k) {
num_min++;
} else if (arr[i] > k) {
num_max++;
}
}
// Here we are calculating the actual
// position of k in the array.
for (int i = 0; i < n; i++) {
if (arr[i] == k) {
pos = i;
break;
}
}
int left, right, mid;
left = 0;
right = n - 1;
// Implementing binary search as
// per the above-discussed cases.
while (left <= right) {
mid = (left + right) / 2;
// If we find the k.
if (arr[mid] == k) {
break;
} else if (arr[mid] > k) {
// If we need minimum
// element swap.
if (pos > mid) {
need_minimum++;
} else // Else the element is
// at the right position.
{
num_min--;
}
left = mid + 1;
} else {
if (pos < mid) // If we need maximum
// element swap.
{
need_maximum++;
} else // Else element is at
// the right position
{
num_max--;
}
right = mid - 1;
}
}
// Calculating the required swaps.
if (need_minimum > need_maximum) {
swaps = swaps + need_maximum;
num_min = num_min - need_maximum;
need_minimum = need_minimum - need_maximum;
need_maximum = 0;
} else {
swaps = swaps + need_minimum;
num_max = num_max - need_minimum;
need_maximum = need_maximum - need_minimum;
need_minimum = 0;
}
// If it is impossible.
if (need_maximum > num_max || need_minimum > num_min) {
return -1;
} else {
return (swaps + need_maximum + need_minimum);
}
}
// Driver function
public static void Main() {
int []arr = {3, 10, 6, 7, 2, 5, 4};
int k = 4;
int n = arr.Length;
Console.WriteLine(findMinimumSwaps(arr, n, k));
}
}
/*This code is contributed by PrinciRaj1992*/
Javascript
<script>
// Javascript program to find Minimum number
// of swaps to get the position of
// the element if we provide an
// unsorted array to binary search.
// Function to find minimum swaps.
function findMinimumSwaps(arr, n, k)
{
let pos, num_min, num_max,
need_minimum, need_maximum, swaps;
num_min = num_max = need_minimum = 0;
need_maximum = swaps = 0;
// Here we are getting number of
// smaller and greater elements of k.
for (let i = 0; i < n; i++) {
if (arr[i] < k)
num_min++;
else if (arr[i] > k)
num_max++;
}
// Here we are calculating the actual
// position of k in the array.
for (let i = 0; i < n; i++) {
if (arr[i] == k) {
pos = i;
break;
}
}
let left, right, mid;
left = 0;
right = n - 1;
// Implementing binary search as
// per the above-discussed cases.
while (left <= right) {
mid = parseInt((left + right) / 2, 10);
// If we find the k.
if (arr[mid] == k) {
break;
}
else if (arr[mid] > k) {
// If we need minimum
// element swap.
if (pos > mid)
need_minimum++;
else
// Else the element is
// at the right position.
num_min--;
left = mid + 1;
}
else {
if (pos < mid)
// If we need maximum
// element swap.
need_maximum++;
else
// Else element is at
// the right position
num_max--;
right = mid - 1;
}
}
// Calculating the required swaps.
if (need_minimum > need_maximum) {
swaps = swaps + need_maximum;
num_min = num_min - need_maximum;
need_minimum = need_minimum - need_maximum;
need_maximum = 0;
}
else {
swaps = swaps + need_minimum;
num_max = num_max - need_minimum;
need_maximum = need_maximum - need_minimum;
need_minimum = 0;
}
// If it is impossible.
if (need_maximum > num_max || need_minimum > num_min)
return -1;
else
return (swaps + need_maximum + need_minimum);
}
let arr = [ 3, 10, 6, 7, 2, 5, 4 ], k = 4;
let n = arr.length;
document.write(findMinimumSwaps(arr, n, k));
// This code is contributed by divyesh072019.
</script>
Producción:
2
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(1)
Publicación traducida automáticamente
Artículo escrito por Sagar Shukla y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA