How to create an intersection with complexity in O(n)?

Question

I need to create a function that makes the intersection between two vectors: vetorA ∩ vetorB and allocates the values found at this intersection in a vetorC!

Rules:

• to) The complexity of the intersection function/method must be:

  O(n), if n > m

  O(m), if m > n

• b) The signature of the intersection function must be:

  void intersecao(char a[], int n, char b[], int m, char c[], int *k)

• c) Default language functions cannot be used for handling of vectors (search, pertinence, insertion, exclusion, ordering, etc.).

I was thinking of using a complexity algorithm O(n) which is termed "Linear time". But this algorithm he makes the comparison "linear" obviously as the name says.

Example:

A = { 'E', 'C', 'B', 'J', 'S', 'F', 'C', 'V', 'G' }
B = { 'G', 'C', 'M', 'W', 'L', 'O' }
C = { 'G', 'C' }

What is my difficulty?

I am trying to develop a logic that meets the requested complexity O(n) and O(m), But I’m having a hard time picking up a particular element of a particular vector, going through this element, comparing all the other given vector. The only solution I can think of would be at least one O(n²).

Illustration of what I’m trying to do:

MY CODE:

bool checkHasStringEqual(char vectorA, char vectorB) {
    string stringA, stringB;
    stringA = toupper(vectorA),
    stringB = toupper(vectorB);

    size_t found = stringA.find(stringB);

    return (found != std::string::npos);
}

void intersection(char a[], char b[], char c[], int n, int m, int *k){
    cout << "VETOR [A]: {" << a << "}" << endl;
    cout << "VETOR [B]: {" << b << "}\n\n" << endl;

    if(n > m) {
        int index = 0;

        for (int i = 0; i < n; i++) {
            if (checkHasStringEqual(a[i], b[index]) && !checkHasStringEqual(b[index], c[index])) {
                k = new int[strlen(c) + 1];
                c[k] = b[index];

                i = 0;
                index++;

                cout << "EH IGUAL: " << a[i] << " == " << b[index] << endl;
            }
        }
    }

    if(m > n) {
        //CÓDIGO
    }
}

Answer 1

An alternative solution would be to create a vector of bool to indicate whether a given element is in vector A or not. Then, the vector B is read and all elements of B that also appear in A would be immediately inserted in vector C. Something of the type:

#include <iostream>

void intersecao(char a[], int n, char b[], int m, char c[], int *k) {

    //cada uma das posições do vetor representa um letra maiúscula
    bool letras[26] = { false };

    /*Primeiro, lê-se o vetor A, identificando-se as letras maiúsculas e, ao mesmo tempo, 
    alterando o valor do elemento correspondente no vetor letras[] para true.   
    DETALHE: em ASCII o número 65 equivale a letra A, então em 'a[1] - 65', há a conversão de ASCII para o índice do vetor letras, no qual A == 0.*/
    for (int i = 0; i < n; i++) {
        letras[a[i] - 65] = true;
    }

    *k = 0;
    //Então, lê-se o vetor B e, caso a letra presente nesse vetor 
    //também conste no vetor A, ela é inserida no vetor C
    for (int i = 0; i < m; i++) {
        if (letras[b[i] - 65]) {
            c[*k] = b[i];
            (*k)++;
            /*caso se deseje evitar a inserção de valores repetidos, pode-se inserir
            a seguinte instrução:
            letras[b[i] - 65] = false;*/
        }
    }
}

int main() {

    char A[] = { 'E', 'C', 'B', 'J', 'S', 'F', 'C', 'V', 'G' }; 

    char B[] = { 'G', 'C', 'M', 'W', 'L', 'O' };    

    char C[9];
    int k = 0;

    intersecao(A, 9, B, 6, C, &k);  

    for (int i = 0; i < k; i++) {
        std::cout << C[i];
    }

    std::cin.get();
    return 0;
}

Some observations: I assumed that the vectors A and B would only contain uppercase letters. Then, it is necessary to note that the above code would need to receive some security modifications, at least to check the values contained in these vectors, otherwise the instruction letras[a[i] - 65] = true can possibly write outside the limits of the array

(Note: I did not enter these security modifications because I wanted to focus on the algorithm. Also how you use the function touper I don’t think you’d have any trouble doing that).

Still about the type of input: if the vectors contained values other than just uppercase letters. The solution could be changed and would continue in O(n), if the possible elements could be previously known, although the use of memory could become a problem, for example, if the vectors were composed of int32_t simply allocate a few gigabites to construct a bool vector to account for all possible integer numbers in this type.

However, if the possible elements could not be previously known, for example if A and B were vectors of strings, then I can only imagine solutions of type O(nLogn), in which, should be done previously the ordering of vector elements with some efficient sorting algorithm.