Cambios mínimos requeridos para hacer dos arreglos idénticos

Posted on by Rudeus Greyrat

Dadas dos arrays,  A y  B con n elementos cada una. La tarea es hacer que estas dos arrays sean idénticas, es decir, para cada una  1\leq i \leq N , queremos hacer  A_{i} = B_{i} . En una sola operación, puede elegir dos números enteros x e y , y reemplazar todas las apariciones de x en ambas arrays con y . Tenga en cuenta que, independientemente del número de ocurrencias reemplazadas, aún se contará como una sola operación. Debe generar el número mínimo de operaciones requeridas.

Ejemplos: 

Input : 1 2 2
        1 2 5
Output: 1
Here, (x, y) = (5, 2) hence ans = 1.

Input : 2 1 1 3 5
        1 2 2 4 5
Output: 2
Here, (x, y) = (1, 2) and (3, 4) thus ans = 2.
Other pairs are also possible.

Este problema se puede resolver con la ayuda de Disjoint Set Union .
Verificaremos todos los elementos de ambas arrays i:e para cada uno  1\leq i \leq N . Si los elementos pertenecen al mismo id , lo omitimos. De lo contrario, hacemos una operación de unión en ambos elementos. Finalmente, la respuesta será la suma de los tamaños de todos los diferentes conjuntos disjuntos formados i:e  respuesta = \sum_{i=1}^{N} (sz[i]-1) . Restamos 1 porque, inicialmente, tomamos el tamaño de cada conjunto como 1. 

A continuación se muestra la implementación del enfoque anterior: 

C++

// C++ program to find minimum changes
// required to make two arrays identical
#include <bits/stdc++.h>
using namespace std;
 
#define N 100010
 
/*  'id': stores parent of a node.
    'sz': stores size of a DSU tree. */
int id[N], sz[N];
 
// Function to assign root
int Root(int idx)
{
    int i = idx;
    while (i != id[i])
        id[i] = id[id[i]], i = id[i];
 
    return i;
}
 
// Function to find Union
void Union(int a, int b)
{
    int i = Root(a), j = Root(b);
 
    if (i != j) {
        if (sz[i] >= sz[j]) {
            id[j] = i, sz[i] += sz[j];
            sz[j] = 0;
        }
        else {
            id[i] = j, sz[j] += sz[i];
            sz[i] = 0;
        }
    }
}
 
// function to find minimum changes required
// to make both array equal.
int minChange(int n, int a[], int b[])
{
 
    // Sets as single elements
    for (int i = 0; i < N; i++)
        id[i] = i, sz[i] = 1;
 
    // Combine items if they belong to different
    // sets.
    for (int i = 0; i < n; ++i)
 
        // true if both elements have different root
        if (Root(a[i]) != Root(b[i]))
            Union(a[i], b[i]); // make root equal
 
    // Find sum sizes of all sets formed.
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (id[i] == i)
            ans += (sz[i] - 1);
 
    return ans;
}
 
// Driver program
int main()
{
 
    int a[] = { 2, 1, 1, 3, 5 }, b[] = { 1, 2, 2, 4, 5 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << minChange(n, a, b);
    return 0;
}

Java

// Java program to find minimum changes
// required to make two arrays identical
 
class GFG{
static int N=100010;
 
/* 'id': stores parent of a node.
    'sz': stores size of a DSU tree. */
static int[] id=new int[100010];
static int[] sz=new int[100010];
 
// Function to assign root
static int Root(int idx)
{
    int i = idx;
    while (i != id[i])
        {
            id[i] = id[id[i]];
            i = id[i];
        }
 
    return i;
}
 
// Function to find Union
static void Union(int a, int b)
{
    int i = Root(a);
    int j = Root(b);
 
    if (i != j) {
        if (sz[i] >= sz[j]) {
            id[j] = i;
            sz[i] += sz[j];
            sz[j] = 0;
        }
        else {
            id[i] = j;
            sz[j] += sz[i];
            sz[i] = 0;
        }
    }
}
 
// function to find minimum changes required
// to make both array equal.
static int minChange(int n, int a[], int b[])
{
 
    // Sets as single elements
    for (int i = 0; i < N; i++)
        {
            id[i] = i;
            sz[i] = 1;
        }
 
    // Combine items if they belong to different
    // sets.
    for (int i = 0; i < n; ++i)
 
        // true if both elements have different root
        if (Root(a[i]) != Root(b[i]))
            Union(a[i], b[i]); // make root equal
 
    // Find sum sizes of all sets formed.
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (id[i] == i)
            ans += (sz[i] - 1);
 
    return ans;
}
 
// Driver program
public static void main(String[] args)
{
 
    int a[] = { 2, 1, 1, 3, 5 }, b[] = { 1, 2, 2, 4, 5 };
    int n = a.length;
    System.out.println(minChange(n, a, b));
}
}
// This code is contributed by mits

Python3

# Python 3 program to find minimum changes
# required to make two arrays identical
 
N = 100010
 
# 'id':stores parent of a node
# 'sz':stores size of a DSU tree
ID = [0 for i in range(N)]
sz = [0 for i in range(N)]
 
# function to assign root
def Root(idx):
    i = idx
    while i != ID[i]:
        ID[i], i = ID[ID[i]], ID[i]
    return i
 
# Function to find Union
def Union(a, b):
    i, j = Root(a), Root(b)
     
    if i != j:
        if sz[i] >= sz[j]:
            ID[j] = i
            sz[i] += sz[j]
            sz[j] = 0
        else:
            ID[i] = j
            sz[j] += sz[i]
            sz[i] = 0
 
# function to find minimum changes
# required to make both array equal
def minChange(n, a, b):
     
    # sets as single elements
    for i in range(N):
        ID[i] = i
        sz[i] = 1
         
    # Combine items if they belong
    # to different sets
    for i in range(n):
         
        # true if both elements have
        # different root
        if Root(a[i]) != Root(b[i]):
            Union(a[i], b[i])
     
    # find sum sizes of all sets formed
    ans = 0
    for i in range(n):
        if ID[i] == i:
            ans += (sz[i] - 1)
     
    return ans
     
# Driver Code
a = [2, 1, 1, 3, 5]
b = [1, 2, 2, 4, 5]
n = len(a)
 
print(minChange(n, a, b))
 
# This code is contributed
# by Mohit kumar 29 (IIIT gwalior)

C#

// C# program to find minimum changes
// required to make two arrays identical
using System;
 
class GFG{
static int N=100010;
 
/* 'id': stores parent of a node.
    'sz': stores size of a DSU tree. */
static int []id=new int[100010];
static int []sz=new int[100010];
 
// Function to assign root
static int Root(int idx)
{
    int i = idx;
    while (i != id[i])
        {
            id[i] = id[id[i]];
            i = id[i];
        }
 
    return i;
}
 
// Function to find Union
static void Union(int a, int b)
{
    int i = Root(a);
    int j = Root(b);
 
    if (i != j) {
        if (sz[i] >= sz[j]) {
            id[j] = i;
            sz[i] += sz[j];
            sz[j] = 0;
        }
        else {
            id[i] = j;
            sz[j] += sz[i];
            sz[i] = 0;
        }
    }
}
 
// function to find minimum changes required
// to make both array equal.
static int minChange(int n, int []a, int []b)
{
 
    // Sets as single elements
    for (int i = 0; i < N; i++)
        {
            id[i] = i;
            sz[i] = 1;
        }
 
    // Combine items if they belong to different
    // sets.
    for (int i = 0; i < n; ++i)
 
        // true if both elements have different root
        if (Root(a[i]) != Root(b[i]))
            Union(a[i], b[i]); // make root equal
 
    // Find sum sizes of all sets formed.
    int ans = 0;
    for (int i = 0; i < n; ++i)
        if (id[i] == i)
            ans += (sz[i] - 1);
 
    return ans;
}
 
// Driver program
public static void Main()
{
 
    int []a = { 2, 1, 1, 3, 5 };
    int []b = { 1, 2, 2, 4, 5 };
    int n = a.Length;
    Console.WriteLine(minChange(n, a, b));
}
}
// This code is contributed by anuj_67..

PHP

<?php
// PHP program to find minimum changes
// required to make two arrays identical
$N = 100010;
 
/* 'id': stores parent of a node.
    'sz': stores size of a DSU tree. */
$id = array_fill(0, $N, NULL);
$sz = array_fill(0, $N, NULL);
 
// Function to assign root
function Root($idx)
{
    global $id;
    $i = $idx;
    while ($i != $id[$i])
    {
        $id[$i] = $id[$id[$i]];
        $i = $id[$i];
    }
 
    return $i;
}
 
// Function to find Union
function Union($a, $b)
{
    global $sz, $id;
    $i = Root($a);
    $j = Root($b);
 
    if ($i != $j)
    {
        if ($sz[$i] >= $sz[$j])
        {
            $id[$j] = $i;
            $sz[$i] += $sz[$j];
            $sz[$j] = 0;
        }
        else
        {
            $id[$i] = $j;
            $sz[$j] += $sz[$i];
            $sz[$i] = 0;
        }
    }
}
 
// function to find minimum changes
// required to make both array equal.
function minChange($n, &$a, &$b)
{
    global $id, $sz, $N;
 
    // Sets as single elements
    for ($i = 0; $i < $N; $i++)
    {
        $id[$i] = $i;
        $sz[$i] = 1;
    }
 
    // Combine items if they belong to
    // different sets.
    for ($i = 0; $i < $n; ++$i)
 
        // true if both elements have
        // different roots
        if (Root($a[$i]) != Root($b[$i]))
            Union($a[$i], $b[$i]); // make root equal
 
    // Find sum sizes of all sets formed.
    $ans = 0;
    for ($i = 0; $i < $n; ++$i)
        if ($id[$i] == $i)
            $ans += ($sz[$i] - 1);
 
    return $ans;
}
 
// Driver Code
$a = array(2, 1, 1, 3, 5);
$b = array(1, 2, 2, 4, 5);
$n = sizeof($a);
echo minChange($n, $a, $b);
 
// This code is contributed by ita_c
?>

Javascript

<script>
// Javascript program to find minimum changes
// required to make two arrays identical
     
    let  N=100010;
    /* 'id': stores parent of a node.
    'sz': stores size of a DSU tree. */
    let id=new Array(100010);
    let sz=new Array(100010);
     
    // Function to assign root
    function Root(idx)
    {
        let i = idx;
        while (i != id[i])
        {
            id[i] = id[id[i]];
            i = id[i];
        }
   
        return i;
    }
     
    // Function to find Union
    function Union(a,b)
    {
        let i = Root(a);
        let j = Root(b);
   
        if (i != j) {
            if (sz[i] >= sz[j]) {
                id[j] = i;
                sz[i] += sz[j];
                sz[j] = 0;
            }
            else {
                id[i] = j;
                sz[j] += sz[i];
                sz[i] = 0;
            }
        }
    }
     
    // function to find minimum changes required
    // to make both array equal.
    function minChange(n,a,b)
    {
        // Sets as single elements
        for (let i = 0; i < N; i++)
        {
            id[i] = i;
            sz[i] = 1;
        }
   
    // Combine items if they belong to different
    // sets.
        for (let i = 0; i < n; ++i)
   
        // true if both elements have different root
        if (Root(a[i]) != Root(b[i]))
            Union(a[i], b[i]); // make root equal
   
    // Find sum sizes of all sets formed.
        let ans = 0;
        for (let i = 0; i < n; ++i)
            if (id[i] == i)
                ans += (sz[i] - 1);
   
        return ans;
    }
     
    // Driver program
    let a=[2, 1, 1, 3, 5 ];
    let b=[ 1, 2, 2, 4, 5 ];
    let n = a.length;
    document.write(minChange(n, a, b));
 
 
// This code is contributed by rag2127
</script>
Producción: 

2

 

Complejidad de tiempo: O(N + n) donde N es el valor máximo posible de un elemento de array y n es el número de elementos en la array.
 

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *