Dadas dos arrays arr[] y brr[] de longitud N , la tarea es encontrar el número mínimo de intercambios de los mismos elementos indexados requeridos, tal elemento ocurre al menos en la mitad de los índices en la array arr[] , es decir, elemento mayoritario . Si no es posible obtener dicho arreglo, imprima «-1» .
Ejemplos:
Entrada: arr[] = {3, 2, 1, 4, 9}, brr[] = {5, 5, 3, 5, 3}
Salida: 2
Explicación:
Los siguientes son los intercambios necesarios:
Intercambio 1: intercambio de arr[ 1] y brr[1] modifica arr[] a {3, 2, 3, 4, 9} y brr[] a {5, 5, 1, 5, 3}.
Intercambio 2: intercambiar arr[5] y brr[5] modifica arr[] a {3, 2, 3, 4, 3} y brr[] a {5, 5, 1, 5, 9}.
Por lo tanto, el número total de intercambios necesarios es 2.Entrada: arr[] = {2, 4, 2}, brr[] = {1, 2, 9}
Salida: 0
Enfoque: siga los pasos a continuación para resolver el problema anterior:
- Inicialice una variable res como INT_MAX que almacena el intercambio mínimo requerido.
- Encuentre el conteo de frecuencia de los elementos de las arrays a[] y b[] usando hashing y guárdelo en el mapa A y B respectivamente.
- Cree una array, crr[] de tamaño 2*N para almacenar todos los elementos de la array arr[] y brr[] .
- Recorra la array crr[] usando la variable i y haga lo siguiente:
- Si la frecuencia de crr[i] en el mapa A es al menos N/2 , entonces el intercambio mínimo requerido es 0 y sale del ciclo e imprime 0 .
- Si la suma de la frecuencia de crr[i] en los mapas A y B es al menos N/2 , actualice res al mínimo de res y (N/2 – A[crr[i]]) .
- Después de los pasos anteriores, si el valor de res sigue siendo INT_MAX , imprima «-1» .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function that counts the minimum
// number of swaps required to make
// half of the element same in a[]
int minMoves(int a[], int b[], int n)
{
// Stores frequency of elements in a[]
// Stores frequency of elements in b[]
unordered_map<int, int> A, B;
// Stores all elements from both arrays
vector<int> c;
// Find the maximum occurrence
// required
int maxOccur = ceil(floor(n)
/ (2 * 1.0));
for (int i = 0; i < n; ++i) {
c.push_back(a[i]);
c.push_back(b[i]);
A[a[i]]++;
// If a[i] == b[i], then no need
// of incrementing in map B
if (b[i] != a[i]) {
B[b[i]]++;
}
}
// Store the minimum number of swaps
int res = INT_MAX;
for (int i = 0; i < c.size(); ++i) {
// Frequency of c[i] in array a
int x = A];
// Frequency of c[i] in array b
int y = B];
// Check the frequency condition
if ((x + y) >= maxOccur) {
// if c[i] is present at
// least half times in array
// a[], then 0 swaps required
if (x >= maxOccur) {
return 0;
}
// maxOccur - x is the count
// of swaps needed to make
// c[i] the majority element
else {
res = min(res, maxOccur - x);
}
}
}
// If not possible
if (res == INT_MAX) {
return -1;
}
// Otherwise
else
return res;
}
// Driver Code
int main()
{
// Given arrays a[] and b[]
int arr[] = { 3, 2, 1, 4, 9 };
int brr[] = { 5, 5, 3, 5, 3 };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
cout << minMoves(arr, brr, N);
return 0;
}
Java
// Java program for the
// above approach
import java.util.*;
class Main{
// Function that counts the minimum
// number of swaps required to make
// half of the element same in a[]
public static int minMoves(int a[],
int b[],
int n)
{
// Stores frequency of elements
// in a[]
// Stores frequency of elements
// in b[]
HashMap<Integer,
Integer> A =
new HashMap<>();
HashMap<Integer,
Integer> B =
new HashMap<>();
// Stores all elements from
// both arrays
Vector<Integer> c =
new Vector<Integer>();
// Find the maximum occurrence
// required
int maxOccur = (int)Math.ceil(
(int)Math.floor(n) /
(2 * 1.0));
for (int i = 0; i < n; ++i)
{
c.add(a[i]);
c.add(b[i]);
if(A.containsKey(a[i]))
{
A.replace(a[i],
A.get(a[i]) + 1);
}
else
{
A.put(a[i], 1);
}
// If a[i] == b[i], then no need
// of incrementing in map B
if (b[i] != a[i])
{
if(B.containsKey(b[i]))
{
B.replace(b[i],
B.get(b[i]) + 1);
}
else
{
B.put(b[i], 1);
}
}
}
// Store the minimum number
// of swaps
int res = Integer.MAX_VALUE;
for (int i = 0; i < c.size(); ++i)
{
// Frequency of c[i] in array a
int x = 0;
if(A.containsKey(c.get(i)))
{
x = A.get(c.get(i));
}
// Frequency of c[i] in array b
int y = 0;
if(B.containsKey(c.get(i)))
{
y = B.get(c.get(i));
}
// Check the frequency
// condition
if ((x + y) >= maxOccur)
{
// if c[i] is present at
// least half times in array
// a[], then 0 swaps required
if (x >= maxOccur)
{
return 0;
}
// maxOccur - x is the count
// of swaps needed to make
// c[i] the majority element
else
{
res = Math.min(res,
maxOccur - x);
}
}
}
// If not possible
if (res == Integer.MAX_VALUE)
{
return -1;
}
// Otherwise
else
return res;
}
// Driver code
public static void main(String[] args)
{
// Given arrays a[] and b[]
int arr[] = {3, 2, 1, 4, 9};
int brr[] = {5, 5, 3, 5, 3};
int N = arr.length;
// Function Call
System.out.println(minMoves(arr, brr, N));
}
}
// This code is contributed by divyeshrabadiya07
Python3
# Python3 program for the above approach
from math import ceil, floor
import sys
# Function that counts the minimum
# number of swaps required to make
# half of the element same in a[]
def minMoves(a, b, n):
# Stores frequency of elements in a[]
# Stores frequency of elements in b[]
A, B = {}, {}
# Stores all elements from both arrays
c = []
# Find the maximum occurrence
# required
maxOccur = ceil(floor(n) / (2 * 1.0))
for i in range(n):
c.append(a[i])
c.append(b[i])
A[a[i]] = A.get(a[i], 0) + 1
# If a[i] == b[i], then no need
# of incrementing in map B
if (b[i] != a[i]):
B[b[i]] = B.get(b[i], 0) + 1
# Store the minimum number of swaps
res = sys.maxsize
for i in range(len(c)):
# Frequency of c[i] in array a
x, y = 0, 0
if c[i] in A:
x = A]
# Frequency of c[i] in array b
if c[i] in B:
y = B]
# Check the frequency condition
if ((x + y) >= maxOccur):
# If c[i] is present at
# least half times in array
# a[], then 0 swaps required
if (x >= maxOccur):
return 0
# maxOccur - x is the count
# of swaps needed to make
# c[i] the majority element
else:
res = min(res, maxOccur - x)
# If not possible
if (res == sys.maxsize):
return -1
# Otherwise
else:
return res
# Driver Code
if __name__ == '__main__':
# Given arrays a[] and b[]
arr = [ 3, 2, 1, 4, 9 ]
brr = [ 5, 5, 3, 5, 3 ]
N = len(arr)
# Function Call
print(minMoves(arr, brr, N))
# This code is contributed by mohit kumar 29
C#
// C# program for the
// above approach
using System;
using System.Collections.Generic;
class GFG{
// Function that counts the minimum
// number of swaps required to make
// half of the element same in []a
public static int minMoves(int []a,
int []b,
int n)
{
// Stores frequency of elements
// in []a
// Stores frequency of elements
// in []b
Dictionary<int,
int> A = new Dictionary<int,
int>();
Dictionary<int,
int> B = new Dictionary<int,
int>();
// Stores all elements from
// both arrays
List<int> c = new List<int>();
// Find the maximum occurrence
// required
int maxOccur = (int)(Math.Ceiling(
(int)(Math.Floor(
(double)n)) / (2 * 1.0)));
for(int i = 0; i < n; ++i)
{
c.Add(a[i]);
c.Add(b[i]);
if (A.ContainsKey(a[i]))
{
A[a[i]] = A[a[i]] + 1;
}
else
{
A.Add(a[i], 1);
}
// If a[i] == b[i], then no need
// of incrementing in map B
if (b[i] != a[i])
{
if (B.ContainsKey(b[i]))
{
B[b[i]]++;
}
else
{
B.Add(b[i], 1);
}
}
}
// Store the minimum number
// of swaps
int res = int.MaxValue;
for(int i = 0; i < c.Count; ++i)
{
// Frequency of c[i] in array a
int x = 0;
if (A.ContainsKey(c[i]))
{
x = A];
}
// Frequency of c[i] in array b
int y = 0;
if (B.ContainsKey(c[i]))
{
y = B];
}
// Check the frequency
// condition
if ((x + y) >= maxOccur)
{
// If c[i] is present at
// least half times in array
// []a, then 0 swaps required
if (x >= maxOccur)
{
return 0;
}
// maxOccur - x is the count
// of swaps needed to make
// c[i] the majority element
else
{
res = Math.Min(res,
maxOccur - x);
}
}
}
// If not possible
if (res == int.MaxValue)
{
return -1;
}
// Otherwise
else
return res;
}
// Driver code
public static void Main(String[] args)
{
// Given arrays []a and []b
int []arr = { 3, 2, 1, 4, 9 };
int []brr = { 5, 5, 3, 5, 3 };
int N = arr.Length;
// Function Call
Console.WriteLine(minMoves(arr, brr, N));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// Javascript program for the above approach
// Function that counts the minimum
// number of swaps required to make
// half of the element same in a[]
function minMoves(a, b, n)
{
// Stores frequency of elements in a[]
// Stores frequency of elements in b[]
var A = new Map(), B = new Map();
// Stores all elements from both arrays
var c = [];
// Find the maximum occurrence
// required
var maxOccur = Math.ceil(Math.floor(n)
/ (2 * 1.0));
for (var i = 0; i < n; ++i) {
c.push(a[i]);
c.push(b[i]);
if(A.has(a[i]))
{
A.set(a[i], A.get(a[i])+1);
}
else
{
A.set(a[i], 1);
}
// If a[i] == b[i], then no need
// of incrementing in map B
if (b[i] != a[i]) {
if(B.has(b[i]))
{
B.set(b[i], B.get(b[i])+1);
}
else
{
B.set(b[i], 1);
}
}
}
// Store the minimum number of swaps
var res = 1000000000;
for (var i = 0; i < c.length; ++i) {
// Frequency of c[i] in array a
var x = A.get(c[i]);
// Frequency of c[i] in array b
var y = B.get(c[i]);
// Check the frequency condition
if ((x + y) >= maxOccur) {
// if c[i] is present at
// least half times in array
// a[], then 0 swaps required
if (x >= maxOccur) {
return 0;
}
// maxOccur - x is the count
// of swaps needed to make
// c[i] the majority element
else {
res = Math.min(res, maxOccur - x);
}
}
}
// If not possible
if (res == 1000000000) {
return -1;
}
// Otherwise
else
return res;
}
// Driver Code
// Given arrays a[] and b[]
var arr = [3, 2, 1, 4, 9];
var brr = [5, 5, 3, 5, 3];
var N = arr.length;
// Function Call
document.write( minMoves(arr, brr, N));
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por ujjwalgoel1103 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA