Voltar

Imprimir linhas únicas em uma dada Matriz Booleana - Estrutura de dados

0 Curtidas

Dada uma matriz binária, imprimir todas as linhas únicas da matriz dada.

Entrada:
{0, 1, 0, 0, 1}
{1, 0, 1, 1, 0}
{0, 1, 0, 0, 1}
{1, 1, 1, 0, 0}

Saída:
0 1 0 0 1
1 0 1 1 0
1 1 1 0 0

Método 1 (simples)
Uma abordagem simples é verificar cada linha com todas as linhas processadas. Imprima a primeira linha. Agora, a partir da segunda linha, para cada linha, a linha de comparação com linhas já processados. Se a linha combina com qualquer uma das linhas processadas, não imprima. Se a linha atual não corresponde com nenhuma linha, imprima.
Complexidade de tempo: O(ROW² x COL)
Espaço auxiliar: O(1)

Método 2 (Uso de Árvore de busca Binária)
Encontre o equivalente decimal de cada linha e insira-o BST. Cada nó da BST conterá dois campos, um campo para o valor decimal, outros para número da linha. Não insira um nó se ele é duplicado. Por fim, atravesse o BST e imprima as linhas correspondentes.
Tempo complexidade: O(ROW x COL + ROW x log (ROW))
Espaço auxiliar: O (ROW)
Este método vai estourar o limite dos números inteiros se o número de colunas for grande.

Método 3 (Uso de Trie)
Uma vez que a matriz é booleana, uma variante da estrutura de dados Trie pode ser usada onde cada nó terá dois filhos para um 0 e 1. Inserir outros para cada fileira
em trie. Se a linha já está lá, não imprima a linha. Se a linha não está lá em Trie, insira-o em Trie e imprimi-lo.

Abaixo está a implementação em C do método 3:

//Given a binary matrix of M X N of integers, you need to return only unique rows of binary array
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ROW 4
#define COL 5
// A Trie node
typedef struct Node
{
    bool isEndOfCol;
    struct Node *child[2]; // Only two children needed for 0 and 1
} Node;

// A utility function to allocate memory for a new Trie node
Node* newNode()
{
    Node* temp = (Node *)malloc( sizeof( Node ) );
    temp->isEndOfCol = 0;
    temp->child[0] = temp->child[1] = NULL;
    return temp;
}
// Inserts a new matrix row to Trie. If row is already
// present, then returns 0, otherwise insets the row and
// return 1
bool insert( Node** root, int (*M)[COL], int row, int col )
{
    // base case
    if ( *root == NULL )
        *root = newNode();
    // Recur if there are more entries in this row
    if ( col < COL )
        return insert ( &( (*root)->child[ M[row][col] ] ), M, row, col+1 );
    else // If all entries of this row are processed
    {
        // unique row found, return 1
        if ( !( (*root)->isEndOfCol ) )
            return (*root)->isEndOfCol = 1;
        // duplicate row found, return 0
        return 0;
    }
}
// A utility function to print a row
void printRow( int (*M)[COL], int row )
{
    int i;
    for( i = 0; i < COL; ++i )
        printf( "%d ", M[row][i] );
    printf("\n");
}
// The main function that prints all unique rows in a
// given matrix.
void findUniqueRows( int (*M)[COL] )
{
    Node* root = NULL; // create an empty Trie
    int i;
    // Iterate through all rows
    for ( i = 0; i < ROW; ++i )
        // insert row to TRIE
        if ( insert(&root, M, i, 0) )
            // unique row found, print it
            printRow( M, i );
}
// Driver program to test above functions
int main()
{
    int M[ROW][COL] = {
        {0, 1, 0, 0, 1},
        {1, 0, 1, 1, 0},
        {0, 1, 0, 0, 1},
        {1, 0, 1, 0, 0}
    };
    findUniqueRows( M );
    return 0;
}

Complexidade de tempo: O( ROW x COL )
Espaço auxiliar: O( ROW x COL )

Fonte:
http://www.geeksforgeeks.org/print-unique-rows/

Problemas relacionados
  Nome Comentário
Ainda não há nenhum problema relacionado a esse conteúdo
Sugestão de livro

Comentários


Postagens neste fórum só são permitidas para membros com conta ativa. Por favor, efetue login or cadastro para postar.