You can use sorting algorithms and intersection and Union techniques, follow these steps in your order:
- Ordain the
Array
- Check the Intersection of
Array
- Join the Intersection of them.
Of Ordination:
You can use an existing algorithm called MergeSort
, where it uses the strategy "divide-to-conquer" and the complexity of it in the best and worst case is O(n log n)
.
Animated example of the functioning of MergeSort
:
Algorithm:
public class WikiMerge<T extends Comparable<T>>{
/**
* Método que recebe um array de inteiros e dois inteiros referentes ao início e ao fim
* da ordenação desse array, o que nos garante o poder de escolher uma faixa do array
* para ser ordenado.
*
* @param array
* @param indiceInicio
* @param indiceFim
*/
public void ordena(T[] array, int indiceInicio, int indiceFim) {
// Condicional que verifica a validade dos parâmetros passados.
if (array != null && indiceInicio < indiceFim && indiceInicio >= 0 &&
indiceFim < array.length && array.length != 0) {
int meio = ((indiceFim + indiceInicio) / 2);
ordena(array, indiceInicio, meio);
ordena(array, meio + 1, indiceFim);
merge(array, indiceInicio, meio, indiceFim);
}
}
/**
* O merge consiste na junção de duas listas já ordenadas.
* Usa um array auxiliar.
*
* @param array
* @param indiceInicio
* @param meio
* @param indiceFim
*/
public void merge(T[] array, int indiceInicio, int meio, int indiceFim) {
T[] auxiliar =(T[]) new Comparable[array.length];
//Copiando o trecho da lista que vai ser ordenada
for (int i = indiceInicio; i <= indiceFim; i++) {
auxiliar[i] = array[i];
}
//Índices auxiliares
int i = indiceInicio;
int j = meio + 1;
int k = indiceInicio;
//Junção das listas ordenadas
while (i <= meio && j <= indiceFim) {
if (auxiliar[i].compareTo(auxiliar[j]) < 0) {
array[k] = auxiliar[i];
i++;
} else {
array[k] = auxiliar[j];
j++;
}
k++;
}
//Append de itens que não foram usados na Junção
while (i <= meio) {
array[k] = auxiliar[i];
i++;
k++;
}
//Append de itens que não foram usados na Junção
while (j <= indiceFim) {
array[k] = auxiliar[j];
j++;
k++;
}
}
}
Intersection
You can use several existing techniques (algorithms) to make the intersection and union, where the complexity of it is O(n+m)
which is equal to O(n)
.
Algorithm of one of the Intersection and Union Techniques:
// Um programa em Java para imprimir união e interseção
/// de duas matrizes não classificadas
import java.util.Arrays;
class UnionAndIntersection
{
//Imprime a união de arr1 [0..m-1] e arr2 [0..n-1]
void printUnion(int arr1[], int arr2[], int m, int n)
{
// Antes de encontrar a união, certifique-se de que arr1 [0..m-1]
// é menor
if (m > n)
{
int tempp[] = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
// Agora arr1 [] é menor
// Ordenar o primeiro array e imprime seus elementos (esses dois
// as etapas podem ser trocadas, pois a ordem na saída não é importante)
Arrays.sort(arr1);
for (int i = 0; i < m; i++)
System.out.print(arr1[i] + " ");
// Pesquisar todos os elementos da matriz maior em uma matriz menor
// e imprime o elemento se não for encontrado
for (int i = 0; i < n; i++)
{
if (binarySearch(arr1, 0, m - 1, arr2[i]) == -1)
System.out.print(arr2[i] + " ");
}
}
// Imprime intersecção de arr1 [0..m-1] e arr2 [0..n-1]
void printIntersection(int arr1[], int arr2[], int m, int n)
{
// Antes de encontrar o cruzamento, certifique-se de que arr1 [0..m-1]
// é menor
if (m > n)
{
int tempp[] = arr1;
arr1 = arr2;
arr2 = tempp;
int temp = m;
m = n;
n = temp;
}
// Agora arr1 [] é menor
// Classificar array menor arr1 [0..m-1]
Arrays.sort(arr1);
// Pesquisar todos os elementos da matriz maior em uma matriz menor
// e imprima o elemento se encontrado
for (int i = 0; i < n; i++)
{
if (binarySearch(arr1, 0, m - 1, arr2[i]) != -1)
System.out.print(arr2[i] + " ");
}
}
// Uma função de pesquisa binária recursiva. Retorna a localização de x em
// dado array arr [l..r] está presente, caso contrário -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
// Se o elemento estiver presente no meio
if (arr[mid] == x)
return mid;
// Se o elemento for menor que o meio, então ele só pode
// estar presente no subarray esquerdo
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else o elemento só pode estar presente no subarray direito
return binarySearch(arr, mid + 1, r, x);
}
// Nós chegamos aqui quando o elemento não está presente no array
return -1;
}
// Programa do driver para testar as funções acima
public static void main(String[] args)
{
UnionAndIntersection u_i = new UnionAndIntersection();
int arr1[] = {7, 1, 5, 2, 3, 6};
int arr2[] = {3, 8, 6, 20, 7};
int m = arr1.length;
int n = arr2.length;
System.out.println("Union of two arrays is ");
u_i.printUnion(arr1, arr2, m, n);
System.out.println("");
System.out.println("Intersection of two arrays is ");
u_i.printIntersection(arr1, arr2, m, n);
}
}
Note:
PS:
- There are several other algorithms to sort, so I suggest that access this link to learn more about them.
- Read carefully the link of intersection and joining techniques, as there are several techniques for which it has its usefulness.
I understand, but comparing and knowing if they are equal just by using the name of the list is not possible? they would already be ordered..
– Marcos Aurelio Binoti