2

Necessito criar uma função que faz a interseção entre dois vetores: vetorA vetorB e aloca os valores encontrados nesta interseção em um vetorC!

Regras:

  • a) A complexidade da função/método intersecao deve ser, obrigatoriamente:

    O(n), se n > m

    O(m), se m > n

  • b) A assinatura da função de interseção deve ser, obrigatoriamente:

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

  • c) Não podem ser usadas funções predefinidas das linguagens para tratamento dos vetores (busca, pertinência, inserção, exclusão, ordenação, etc.).

Eu estava pensando em utilizar um algoritmo de complexidade O(n) o qual é denominado "Tempo linear". Porém este algoritmo ele faz a comparação "linear" obviamente como o nome diz.

Exemplo:

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

Qual a minha dificuldade?

Estou tentando desenvolver uma lógica que atenda a complexidade pedida O(n) e O(m), porém estou com dificuldade em pegar um determinado elemento de um determinado vetor, percorrer com este elemento, comparando todo o outro determinado vetor. A única solução que consigo pensar seria pelo menos um O(n²).

Ilustração do que estou tentando fazer: inserir a descrição da imagem aqui

MEU CÓDIGO:

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
    }
}
4
  • não acredito que seja possível fazer isso em O(n)...meu palpite é O(m*n), que não é ruim, acho eu
    – zentrunix
    25/05/2019 às 21:34
  • @zentrunix è possível fazer com o algoritmo que citei acima, porém ele busca e compara linearmente por exemplo: a[0] == b[0], a[1] == b[1] e por aí vai, eu preciso tentar modifica-lo para que “trave” o índice de um vetor e busque e compare tudo por exemplo a[0] == b[0] , a[1] == b[0] e por aí vai.
    – user148754
    25/05/2019 às 21:51
  • 1
    Creio que você só consiga fazer tal algoritmo se ambos os vetores estiverem ordenados. Aí vira um problema de linha balanceada.
    – anonimo
    14/06/2019 às 2:34
  • @anonimo e ai amigo, tudo bem? Eu acabei de responder a minha pergunta também com o algoritmo já pronto, obrigado por tudo!
    – user148754
    14/06/2019 às 2:35

1 Resposta 1

2

Uma solução alternativa seria criar um vetor de bool para informar se determinado elemento consta, ou não, no vetorA. Em seguida, lê-se o vetorB e todos os elementos de B que também constassem em A seriam imediatamente inseridos no vetorC. Algo do tipo:

#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;
}

Algumas observações: eu assumi que os vetores A e B somente conteriam letras maiúsculas. Então, é necessário observar que o código acima precisaria receber algumas modificações de segurança, ao menos para verificar os valores contidos nesses vetores, do contrário, a instrução letras[a[i] - 65] = true pode eventualmente escrever fora dos limites do array

(Observação: eu não inseri essas modificações de segurança, porque queria me focar no algorítimo. Além do mais como você usa a função touper acho que você não teria nenhuma dificuldade em fazer isso).

Ainda sobre o tipo de entrada: caso os vetores contivessem outros valores que não apenas letras maiúsculas. A solução poderia ser alterada e continuaria em O(n), se os elementos possíveis pudessem ser previamente conhecidos, embora o uso de memória pudesse se tornar um problema, por exemplo, se os vetores fossem compostos por int32_t bastaria alocar alguns gigabites para construir um vetor de bool para dar conta de todos os números inteiros possíveis nesse tipo.

Contudo, caso os elementos possíveis não pudessem ser previamente conhecidos, por exemplo, se A e B fossem vetores de strings, aí eu só consigo imaginar soluções do tipo O(nLogn), nas quais, deveria ser feita previamente a ordenação dos elementos dos vetores com algum algorítimo de ordenação eficiente.

4
  • você está percorrendo o vetor A (tamanho n) e depois o vetor B (tamanho m), isso implica que a complexidade vai ser O(n+m) e não O(n), como disse no comentário da pergunta...tá certo que a complexidade ainda é linear, o que é bom, mas é linear em A + B, e não apenas em A
    – zentrunix
    26/05/2019 às 10:05
  • @zentrunix, o(n+m) = o(n) nesse caso. 26/05/2019 às 14:04
  • 2
    Se n > m, então O(m + n) = O(n + n) = O(n) Se m > n, o resultado é análogo.
    – MrParrot
    30/05/2019 às 13:16
  • @zentrunix O(n+m) é igual a O(n).
    – user148754
    14/06/2019 às 2:36

Você deve fazer log-in para responder a esta pergunta.