Dados dos conjuntos representados por dos arrays, ¿cómo verificar si los dos conjuntos dados son disjuntos o no? Se puede suponer que las arrays dadas no tienen duplicados.
Input: set1[] = {12, 34, 11, 9, 3}
set2[] = {2, 1, 3, 5}
Output: Not Disjoint
3 is common in two sets.
Input: set1[] = {12, 34, 11, 9, 3}
set2[] = {7, 2, 1, 5}
Output: Yes, Disjoint
There is no common element in two sets.
Hay muchos métodos para resolver este problema, es una buena prueba para verificar cuántas soluciones puedes adivinar.
Método 1 (Simple): iterar a través de cada elemento del primer conjunto y buscarlo en otro conjunto, si se encuentra algún elemento, devolver falso. Si no se encuentra ningún elemento, devuelve verdadero. La complejidad temporal de este método es O(mn).
A continuación se muestra la implementación de la idea anterior.
C++
// A Simple C++ program to check if two sets are disjoint
#include<bits/stdc++.h>
using namespace std;
// Returns true if set1[] and set2[] are disjoint, else false
bool areDisjoint(int set1[], int set2[], int m, int n)
{
// Take every element of set1[] and search it in set2
for (int i=0; i<m; i++)
for (int j=0; j<n; j++)
if (set1[i] == set2[j])
return false;
// If no element of set1 is present in set2
return true;
}
// Driver program to test above function
int main()
{
int set1[] = {12, 34, 11, 9, 3};
int set2[] = {7, 2, 1, 5};
int m = sizeof(set1)/sizeof(set1[0]);
int n = sizeof(set2)/sizeof(set2[0]);
areDisjoint(set1, set2, m, n)? cout << "Yes" : cout << " No";
return 0;
}
Java
// Java program to check if two sets are disjoint
public class disjoint1
{
// Returns true if set1[] and set2[] are
// disjoint, else false
boolean aredisjoint(int set1[], int set2[])
{
// Take every element of set1[] and
// search it in set2
for (int i = 0; i < set1.length; i++)
{
for (int j = 0; j < set2.length; j++)
{
if (set1[i] == set2[j])
return false;
}
}
// If no element of set1 is present in set2
return true;
}
// Driver program to test above function
public static void main(String[] args)
{
disjoint1 dis = new disjoint1();
int set1[] = { 12, 34, 11, 9, 3 };
int set2[] = { 7, 2, 1, 5 };
boolean result = dis.aredisjoint(set1, set2);
if (result)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by Rishabh Mahrsee
Python
# A Simple python 3 program to check
# if two sets are disjoint
# Returns true if set1[] and set2[] are disjoint, else false
def areDisjoint(set1, set2, m, n):
# Take every element of set1[] and search it in set2
for i in range(0, m):
for j in range(0, n):
if (set1[i] == set2[j]):
return False
# If no element of set1 is present in set2
return True
# Driver program
set1 = [12, 34, 11, 9, 3]
set2 = [7, 2, 1, 5]
m = len(set1)
n = len(set2)
print("yes") if areDisjoint(set1, set2, m, n) else(" No")
# This code ia contributed by Smitha Dinesh Semwal
C#
// C# program to check if two
// sets are disjoint
using System;
class GFG
{
// Returns true if set1[] and set2[]
// are disjoint, else false
public virtual bool aredisjoint(int[] set1,
int[] set2)
{
// Take every element of set1[]
// and search it in set2
for (int i = 0; i < set1.Length; i++)
{
for (int j = 0;
j < set2.Length; j++)
{
if (set1[i] == set2[j])
{
return false;
}
}
}
// If no element of set1 is
// present in set2
return true;
}
// Driver Code
public static void Main(string[] args)
{
GFG dis = new GFG();
int[] set1 = new int[] {12, 34, 11, 9, 3};
int[] set2 = new int[] {7, 2, 1, 5};
bool result = dis.aredisjoint(set1, set2);
if (result)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
// This code is contributed by Shrikant13
PHP
<?php
// A Simple PHP program to check
// if two sets are disjoint
// Returns true if set1[] and set2[]
// are disjoint, else false
function areDisjoint($set1, $set2, $m, $n)
{
// Take every element of set1[]
// and search it in set2
for ($i = 0; $i < $m; $i++)
for ($j = 0; $j < $n; $j++)
if ($set1[$i] == $set2[$j])
return false;
// If no element of set1 is
// present in set2
return true;
}
// Driver Code
$set1 = array(12, 34, 11, 9, 3);
$set2 = array(7, 2, 1, 5);
$m = sizeof($set1);
$n = sizeof($set2);
if(areDisjoint($set1, $set2,
$m, $n) == true)
echo "Yes";
else
echo " No";
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript program to check if two sets are disjoint
// Returns true if set1[] and set2[] are
// disjoint, else false
function aredisjoint(set1,set2)
{
// Take every element of set1[] and
// search it in set2
for (let i = 0; i < set1.length; i++)
{
for (let j = 0; j < set2.length; j++)
{
if (set1[i] == set2[j])
return false;
}
}
// If no element of set1 is present in set2
return true;
}
// Driver program to test above function
let set1=[12, 34, 11, 9, 3];
let set2=[7, 2, 1, 5];
result = aredisjoint(set1, set2);
if (result)
document.write("Yes");
else
document.write("No");
// This code is contributed by avanitrachhadiya2155
</script>
Producción
Yes
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Método 2 (usar clasificación y fusión) :
- Ordenar los conjuntos primero y segundo.
- Utilice fusionar como el proceso para comparar elementos.
A continuación se muestra la implementación de la idea anterior.
C++
// A Simple C++ program to check if two sets are disjoint
#include<bits/stdc++.h>
using namespace std;
// Returns true if set1[] and set2[] are disjoint, else false
bool areDisjoint(int set1[], int set2[], int m, int n)
{
// Sort the given two sets
sort(set1, set1+m);
sort(set2, set2+n);
// Check for same elements using merge like process
int i = 0, j = 0;
while (i < m && j < n)
{
if (set1[i] < set2[j])
i++;
else if (set2[j] < set1[i])
j++;
else /* if set1[i] == set2[j] */
return false;
}
return true;
}
// Driver program to test above function
int main()
{
int set1[] = {12, 34, 11, 9, 3};
int set2[] = {7, 2, 1, 5};
int m = sizeof(set1)/sizeof(set1[0]);
int n = sizeof(set2)/sizeof(set2[0]);
areDisjoint(set1, set2, m, n)? cout << "Yes" : cout << " No";
return 0;
}
Java
// Java program to check if two sets are disjoint
import java.util.Arrays;
public class disjoint1
{
// Returns true if set1[] and set2[] are
// disjoint, else false
boolean aredisjoint(int set1[], int set2[])
{
int i=0,j=0;
// Sort the given two sets
Arrays.sort(set1);
Arrays.sort(set2);
// Check for same elements using
// merge like process
while(i<set1.length && j<set2.length)
{
if(set1[i]<set2[j])
i++;
else if(set1[i]>set2[j])
j++;
else
return false;
}
return true;
}
// Driver program to test above function
public static void main(String[] args)
{
disjoint1 dis = new disjoint1();
int set1[] = { 12, 34, 11, 9, 3 };
int set2[] = { 7, 2, 1, 5 };
boolean result = dis.aredisjoint(set1, set2);
if (result)
System.out.println("YES");
else
System.out.println("NO");
}
}
// This code is contributed by Rishabh Mahrsee
Python3
# A Simple Python 3 program to check
# if two sets are disjoint
# Returns true if set1[] and set2[]
# are disjoint, else false
def areDisjoint(set1, set2, m, n):
# Sort the given two sets
set1.sort()
set2.sort()
# Check for same elements
# using merge like process
i = 0; j = 0
while (i < m and j < n):
if (set1[i] < set2[j]):
i += 1
elif (set2[j] < set1[i]):
j += 1
else: # if set1[i] == set2[j]
return False
return True
# Driver Code
set1 = [12, 34, 11, 9, 3]
set2 = [7, 2, 1, 5]
m = len(set1)
n = len(set2)
print("Yes") if areDisjoint(set1, set2, m, n) else print("No")
# This code is contributed by Smitha Dinesh Semwal
C#
// C# program to check if two sets are disjoint
using System;
public class disjoint1
{
// Returns true if set1[] and set2[] are
// disjoint, else false
Boolean aredisjoint(int []set1, int []set2)
{
int i = 0, j = 0;
// Sort the given two sets
Array.Sort(set1);
Array.Sort(set2);
// Check for same elements using
// merge like process
while(i < set1.Length && j < set2.Length)
{
if(set1[i] < set2[j])
i++;
else if(set1[i] > set2[j])
j++;
else
return false;
}
return true;
}
// Driver code
public static void Main(String[] args)
{
disjoint1 dis = new disjoint1();
int []set1 = { 12, 34, 11, 9, 3 };
int []set2 = { 7, 2, 1, 5 };
Boolean result = dis.aredisjoint(set1, set2);
if (result)
Console.WriteLine("YES");
else
Console.WriteLine("NO");
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// Javascript program to check if two
// sets are disjoint
// Returns true if set1[] and set2[] are
// disjoint, else false
function aredisjoint(set1, set2)
{
let i = 0, j = 0;
// Sort the given two sets
set1.sort(function(a, b){return a - b});
set2.sort(function(a, b){return a - b});
// Check for same elements using
// merge like process
while (i < set1.length && j < set2.length)
{
if (set1[i] < set2[j])
i++;
else if (set1[i] > set2[j])
j++;
else
return false;
}
return true;
}
// Driver code
let set1 = [ 12, 34, 11, 9, 3 ];
let set2 = [ 7, 2, 1, 5 ];
result = aredisjoint(set1, set2);
if (result)
document.write("YES");
else
document.write("NO");
// This code is contributed by rag2127
</script>
Producción
Yes
La complejidad temporal de la solución anterior es O(mLogm + nLogn).
La solución anterior primero ordena ambos conjuntos y luego toma O(m+n) tiempo para encontrar la intersección. Si sabemos que los conjuntos de entrada están ordenados, entonces este método es el mejor entre todos.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Método 3 (Usar clasificación y búsqueda binaria):
Esto es similar al método 1. En lugar de una búsqueda lineal, usamos Binary Search .
- Ordenar primer conjunto.
- Recorra todos los elementos del segundo conjunto y utilice la búsqueda binaria para buscar todos los elementos del primer conjunto. Si se encuentra un elemento, devuélvalo.
La complejidad temporal de este método es O(mLogm + nLogm)
Método 4 (usar árbol de búsqueda binario):
- Cree un árbol de búsqueda binario autoequilibrado ( Red Black , AVL , Splay , etc.) de todos los elementos del primer conjunto.
- Iterar a través de todos los elementos del segundo conjunto y buscar cada elemento en el árbol de búsqueda binario construido anteriormente. Si se encuentra el elemento, devuelve falso.
- Si todos los elementos están ausentes, devuelve verdadero.
La complejidad temporal de este método es O(mLogm + nLogm).
Método 5 (usar hashing):
- Cree una tabla hash vacía.
- Iterar a través del primer conjunto y almacenar cada elemento en la tabla hash.
- Repita el segundo conjunto y verifique si hay algún elemento presente en la tabla hash. Si está presente, devuelve falso; de lo contrario, ignora el elemento.
- Si todos los elementos del segundo conjunto no están presentes en la tabla hash, devuelve verdadero.
A continuación se muestra la implementación de este método.
C++
/* C++ program to check if two sets are distinct or not */
#include<bits/stdc++.h>
using namespace std;
// This function prints all distinct elements
bool areDisjoint(int set1[], int set2[], int n1, int n2)
{
// Creates an empty hashset
set<int> myset;
// Traverse the first set and store its elements in hash
for (int i = 0; i < n1; i++)
myset.insert(set1[i]);
// Traverse the second set and check if any element of it
// is already in hash or not.
for (int i = 0; i < n2; i++)
if (myset.find(set2[i]) != myset.end())
return false;
return true;
}
// Driver method to test above method
int main()
{
int set1[] = {10, 5, 3, 4, 6};
int set2[] = {8, 7, 9, 3};
int n1 = sizeof(set1) / sizeof(set1[0]);
int n2 = sizeof(set2) / sizeof(set2[0]);
if (areDisjoint(set1, set2, n1, n2))
cout << "Yes";
else
cout << "No";
}
//This article is contributed by Chhavi
Java
/* Java program to check if two sets are distinct or not */
import java.util.*;
class Main
{
// This function prints all distinct elements
static boolean areDisjoint(int set1[], int set2[])
{
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Traverse the first set and store its elements in hash
for (int i=0; i<set1.length; i++)
set.add(set1[i]);
// Traverse the second set and check if any element of it
// is already in hash or not.
for (int i=0; i<set2.length; i++)
if (set.contains(set2[i]))
return false;
return true;
}
// Driver method to test above method
public static void main (String[] args)
{
int set1[] = {10, 5, 3, 4, 6};
int set2[] = {8, 7, 9, 3};
if (areDisjoint(set1, set2))
System.out.println("Yes");
else
System.out.println("No");
}
}
Python3
# Python3 program to
# check if two sets are
# distinct or not
# This function prints
# all distinct elements
def areDisjoint(set1, set2,
n1, n2):
# Creates an empty hashset
myset = set([])
# Traverse the first set
# and store its elements in hash
for i in range (n1):
myset.add(set1[i])
# Traverse the second set
# and check if any element of it
# is already in hash or not.
for i in range (n2):
if (set2[i] in myset):
return False
return True
# Driver method to test above method
if __name__ == "__main__":
set1 = [10, 5, 3, 4, 6]
set2 = [8, 7, 9, 3]
n1 = len(set1)
n2 = len(set2)
if (areDisjoint(set1, set2,
n1, n2)):
print ("Yes")
else:
print("No")
# This code is contributed by Chitranayal
C#
using System;
using System.Collections.Generic;
/* C# program to check if two sets are distinct or not */
public class GFG
{
// This function prints all distinct elements
public static bool areDisjoint(int[] set1, int[] set2)
{
// Creates an empty hashset
HashSet<int> set = new HashSet<int>();
// Traverse the first set and store its elements in hash
for (int i = 0; i < set1.Length; i++)
{
set.Add(set1[i]);
}
// Traverse the second set and check if any element of it
// is already in hash or not.
for (int i = 0; i < set2.Length; i++)
{
if (set.Contains(set2[i]))
{
return false;
}
}
return true;
}
// Driver method to test above method
public static void Main(string[] args)
{
int[] set1 = new int[] {10, 5, 3, 4, 6};
int[] set2 = new int[] {8, 7, 9, 3};
if (areDisjoint(set1, set2))
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
}
//This code is contributed by Shrikant13
Javascript
<script>
/* Javascript program to check if two sets are distinct or not */
// This function prints all distinct elements
function areDisjoint(set1,set2)
{
// Creates an empty hashset
let set = new Set();
// Traverse the first set and store its elements in hash
for (let i = 0; i < set1.length; i++)
set.add(set1[i]);
// Traverse the second set and check if any element of it
// is already in hash or not.
for (let i = 0; i < set2.length; i++)
if (set.has(set2[i]))
return false;
return true;
}
// Driver method to test above method
let set1 = [10, 5, 3, 4, 6];
let set2 = [8, 7, 9, 3];
if (areDisjoint(set1, set2))
document.write("Yes");
else
document.write("No");
// This code is contributed by ab2127
</script>
Producción
No
La complejidad temporal de la implementación anterior es O(m+n) bajo el supuesto de que las operaciones de conjunto hash como add() y contains() funcionan en tiempo O(1).
Espacio Auxiliar: O(n)
El espacio adicional se utiliza para almacenar los elementos del conjunto.
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