Filter common elements in two Arrangements

Question

How do I achieve a third arrangement with the intersection (common elements between the two arrangements) between two arrangements without repetition?

int [] a = {1,2,3,4,5,6,7};    // arranjo 1
int [] b = {0,1,2,3};          // arranjo 2

int [] c = {1,2,3};            // arranjo de intersecção

Answer 1

In case you wish "common elements" discards me the possibility of thinking in arrangement. By the concept that I am accustomed to arrangement order matters. At an intersection, order is totally irrelevant.

For example, the arrangements {0,1} and {1,0} are different. If they are treated as ensembles, however, they are the same sets. I do not know what would be the formal definition of intersection for arrangements, but for sets it is so:

If you have no limitation with the Java you are using, you can use the Set directly and solve your problem. Something like this (Java version 8):

int []a = {1, 2, 3, 4, 5, 6, 7 };
int []b = {0, 1, 2, 3};

// cria um objeto da classe Set sobre o array a
Set<Integer> setA = IntStream.of(a).boxed().collect(Collectors.toSet());
// cria um objeto da classe Set sobre o array b
Set<Integer> setB = IntStream.of(b).boxed().collect(Collectors.toSet());

// determina a interseção: verifica se os elementos de a estão em b, transformando em array logo em seguida
int []c = setA.stream().filter(b::contains).mapToInt(Integer::intValue).toArray();

---

Now, this seems to me an exercise proposed by a teacher so that you develop all the logic behind it, using the minimum of external implementations of the subject. So, can I assume it’s all with you? That is, all code being executed comes from your keyboard?

Well, the first step would be to find a way to survive the limitation of the set size. I propose a filthy, ingenious nut solution: we create a rough vector of the maximum possible size and operate on top of it. So, since we count all the elements of the intersection, we create a vector of appropriate size and play from the draft to the new array the interesting part:

int []a = {1, 2, 3, 4, 5, 6, 7 };
int []b = {0, 1, 2, 3};

int []rascunho = new int[a.length < b.length? a.length: b.length];
int tamanhoIntersecoesNoRascunho = 0;

// iterando sobre os elementos no vetor a
for (int elA: a) {
  // primeiro, devo verificar se já foi inserido no rascunho para não repetir...
  boolean contidoRascunho = false;
  for (int i = 0; i < tamanhoIntersecoesNoRascunho; i++) {
    // sim, já fora inserido no rascunho
    if (elA == rascunho[i]) {
      contidoRascunho  = true;
      break;
    }

    // se já está no rascunho, vá para o próximo elemento a ser processado
    if (contidoRascunho) {
      continue;
    }

    // verifica se pertence ao outro conjunto
    for (int elB: b) {
      // foi detectada a interseção
      if (elA == elB) {
        rascunho[tamanhoIntersecoesNoRascunho] = elA;
        tamanhoIntersecoesNoRascunho++;
        break;
      }
    }
  }
}

// criando o vetor final, de tamanho adequado
inc []c = new int[tamanhoIntersecoesNoRascunho];
for (int i = 0; i < tamanhoIntersecoesNoRascunho; i++) {
  c[i] = rascunho[i];
}

This solution simply works, but it (in its present incarnation) is bad for several reasons:

• its running time is o(n * m), being n the size of the first set and m the size of the second set; I think it will get a little worse if it has a large intersection, but that would not change the asymptotic complexity
• requires extra memory expenditure, even if it is plausible that this space at the end is not used

You can even improve part of the runtime by using the logic of initially preprocessing the vectors to get them in ascending order. In this case, however, note that the iteration should be distinct. Read more [1] [2]. Abstracting the ordering part, this would be the detection:

int []a = {1, 2, 3, 4, 5, 6, 7 };
int []b = {0, 1, 2, 3};

// ... rotina misteriosa que ordena a e b ...

int i = 0;
int j = 0;
int idxRascunho = 0;

int []rascunho = new int[a.length < b.length? a.length: b.length];
int ultimoElementoAdicionado = 0;

while (i < a.length && j < b.length) {
  if (a[i] == b[j]) {
    int candidato = a[i];

    if (idxRascunho == 0 || ultimoElementoAdicionado != candidato) {
      rascunho[idxRascunho] = candidato;
      idxRascunho++;
    }

    i++;
    j++;
  }  else if (a[i] < b[j]) {
    i++;
  } else { // a[i] > b[j]...
    j++;
  }
}

// criando o vetor final, de tamanho adequado
inc []c = new int[idxRascunho];
for (int i = 0; i < idxRascunho; i++) {
  c[i] = rascunho[i];
}

This solution improves the performance part, but still has memory problem...

To solve this, how about a linked list? So, assuming the code is totally ours, we can make a linked list. In case, our list will be extremely simple and each node will contain only 3 information:

1. the number he carries with him
2. the pointer to the next element in the list (null means end of list)
3. the size of the list so far, counting the current node

We can add a utility method to it that turns the list into an integer array.

Thus, our linked list node class can be defined like this:

class Nodo {
  final Nodo proximo;
  final int tamanho;
  final int conteudo;

  // para construir um novo nó, só preciso ser informado de seu conteúdo e do vizinho
  Nodo(int conteudo, Nodo proximo) {
    this.conteudo = conteudo;
    this.proximo = proximo;
    this.tamanho = (proximo != null? proximo.tamanho: 0) + 1;
  }

  static int[] toArray(Nodo nodo) {
    if (nodo == null) {
      return new int[0];
    }
    int []vetor = new int[nodo.tamanho];
    for (Nodo it = nodo; it != null; it = it.proximo) {
      // como armazenamos em cada nó o tamanho do lista que se segue + 1,
      // então se pusermos o seu conteúdo na posição it.tamanho-1 manteremos
      // a ordem de inserção dos nodos dentro do vetor, então o vetor
      // gerado estará ordenada
      vetor[it.tamanho - 1] = it.conteudo;
    }
    return vetor;
  }
}

Since the linked list necessarily contains the largest element discovered at the intersection, then we can create the following utility function to know if, by chance, the element has already been inserted at the intersection:

private static boolean candidatoEhNovidade(int candidato, Nodo ultimoNodo) {
  // se está nulo é porque não tem elementos na interseção
  if (ultimoNodo == null) {
    return true;
  } else {
    return candidato != ultimoNodo.conteudo;
  }
}

So on top of that, we can give an abstraction into a method that does list maintenance by returning the new head of the list:

private static Nodo insereSeNovidade(int candidato, Nodo ultimoNodo) {
  if (candidatoEhNovidade(candidato, ultimoNodo)) {
    return new Nodo(candidato, ultimoNodo);
  } else {
    // nada a fazer, então a lista continua no mesmo estado
    return ultimoNodo;
  }
}

And the heart of the show would be this:

int []a = {1, 2, 3, 4, 5, 6, 7 };
int []b = {0, 1, 2, 3};

// ... rotina misteriosa que ordena a e b ...

int i = 0;
int j = 0;
Nodo cabecaLista = null;

while (i < a.length && j < b.length) {
  if (a[i] == b[j]) {
    cabecaLista = insereSeNovidade(a[i], cabecaLista);

    i++;
    j++;
  }  else if (a[i] < b[j]) {
    i++;
  } else { // a[i] > b[j]...
    j++;
  }
}

// criando o vetor final, de tamanho adequado
inc []c = Nodo.toArray(cabecaLista);

Thus, without making use of anything from the standard Java library (except, perhaps, the sorting gap), we were able to create the list in time o(n log n) and using memory asymptotically equal to the size of the intersection between the two sets.

Answer 2

Because the array limitation needs to be started already with its size, however it is not possible to identify the common amount of elements of the two initial arrays, I believe that the solution below can be valid:

int [] a = {1,2,3,4,5,6,7};    // arranjo 1
int [] b = {0,1,2,3};          // arranjo 2
String intersec = "";

for(int i = 0; i < a.length; i++) {
    for(int y = 0; y < b.length; y++){
        if(a[i] == b[y])
            intersec += a[i] + ";";
    }
}

String[] intersecao = intersec.split(";");

System.out.println(Arrays.asList(intersecao));

See it working on ideone: https://ideone.com/VuLuBJ

If you need the resulting array with integer, you can follow the hint of Soen’s reply which, using java-8 streams, converts the string array to int:

int[] arrayInt = Arrays.stream(intersecao).mapToInt(Integer::parseInt).toArray();