Рубрики

Печать уникальных строк в заданной логической матрице

Для заданной двоичной матрицы выведите все уникальные строки данной матрицы.
Пример:

Input:
    {0, 1, 0, 0, 1}
        {1, 0, 1, 1, 0}
        {0, 1, 0, 0, 1}
        {1, 1, 1, 0, 0}
Output:
    0 1 0 0 1 
    1 0 1 1 0 
    1 1 1 0 0 

Способ 1 (простой)
Простой подход заключается в проверке каждой строки со всеми обработанными строками. Распечатать первый ряд. Теперь, начиная со второй строки, для каждой строки сравните строку с уже обработанными строками. Если строка соответствует какой-либо из обработанных строк, не печатайте ее. Если текущая строка не совпадает ни с одной строкой, выведите ее.

Сложность времени: O (ROW ^ 2 x COL)
Вспомогательное пространство: O (1)

Метод 2 (Использование бинарного дерева поиска)
Найдите десятичный эквивалент каждой строки и вставьте ее в BST. Каждый узел BST будет содержать два поля, одно поле для десятичного значения, другое для номера строки. Не вставляйте узел, если он дублирован. Наконец, пройдите BST и напечатайте соответствующие строки.

Временная сложность: O (ROW x COL + ROW x log (ROW))
Вспомогательное пространство: O (ROW)

Этот метод приведет к переполнению целого числа, если количество столбцов велико.

Метод 3 (Использовать структуру данных Trie)
Поскольку матрица является логической, можно использовать вариант структуры данных Trie, где каждый узел будет иметь двух дочерних элементов, один для 0 и другой для 1. Вставьте каждую строку в Trie. Если строка уже есть, не печатайте строку. Если в Trie нет строки, вставьте ее в Trie и распечатайте.

Ниже приведена реализация способа 3.

C ++

// Дана двоичная матрица из MXN целых чисел,
// вам нужно возвращать только уникальные строки двоичного массива
#include <bits/stdc++.h>

using namespace std;

#define ROW 4 
#define COL 5 

  
// Узел Trie

class Node 

    public:

    bool isEndOfCol; 

    Node *child[2]; // Для 0 и 1 нужны только двое детей

} ; 

  

  
// Вспомогательная функция для выделения памяти
// для нового узла Trie
Node* newNode() 

    Node* temp = new Node(); 

    temp->isEndOfCol = 0; 

    temp->child[0] = temp->child[1] = NULL; 

    return temp; 

  
// Вставляет новую строку матрицы в Trie.
// Если строка уже присутствует,
// затем возвращает 0, иначе вставляет строку и
// возвращаем 1

bool insert(Node** root, int (*M)[COL], 

                int row, int col ) 

    // базовый вариант

    if (*root == NULL) 

        *root = newNode(); 

  

    // Повторять, если в этой строке больше записей

    if (col < COL) 

        return insert (&((*root)->child[M[row][col]]), 

                                        M, row, col + 1); 

  

    else // Если все записи этой строки обработаны

    

        // найдена уникальная строка, возвращаем 1

        if (!((*root)->isEndOfCol)) 

            return (*root)->isEndOfCol = 1; 

  

        // найдена повторяющаяся строка, возвращаем 0

        return 0; 

    

  
// Вспомогательная функция для печати строки

void printRow(int(*M)[COL], int row) 

    int i; 

    for(i = 0; i < COL; ++i) 

        cout << M[row][i] << " "

    cout << endl;

  
// Основная функция, которая печатает
// все уникальные строки в данной матрице.

void findUniqueRows(int (*M)[COL]) 

    Node* root = NULL; // создаем пустой Trie

    int i; 

  

    // Итерация по всем строкам

    for (i = 0; i < ROW; ++i) 

      

        // вставить строку в TRIE

        if (insert(&root, M, i, 0))

          

            // найдена уникальная строка, распечатать

            printRow(M, i); 

  
// Код драйвера

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; 

  
// Этот код предоставлен rathbhupendra

С

// Учитывая бинарную матрицу MXN целых чисел, вам нужно возвращать только уникальные строки двоичного массива
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

  
#define ROW 4
#define COL 5

  
// Узел Trie

typedef struct Node

{

    bool isEndOfCol;

    struct Node *child[2]; // Для 0 и 1 нужны только двое детей

} Node;

  

  
// Вспомогательная функция для выделения памяти для нового узла Trie
Node* newNode()
{

    Node* temp = (Node *)malloc( sizeof( Node ) );

    temp->isEndOfCol = 0;

    temp->child[0] = temp->child[1] = NULL;

    return temp;

}

  
// Вставляет новую строку матрицы в Trie. Если строка уже
// присутствует, затем возвращает 0, иначе вставляет строку и
// возвращаем 1

bool insert( Node** root, int (*M)[COL], int row, int col )

{

    // базовый вариант

    if ( *root == NULL )

        *root = newNode();

  

    // Повторять, если в этой строке больше записей

    if ( col < COL )

        return insert ( &( (*root)->child[ M[row][col] ] ), M, row, col+1 );

  

    else // Если все записи этой строки обработаны

    {

        // найдена уникальная строка, возвращаем 1

        if ( !( (*root)->isEndOfCol ) )

            return (*root)->isEndOfCol = 1;

  

        // найдена повторяющаяся строка, возвращаем 0

        return 0;

    }

}

  
// Вспомогательная функция для печати строки

void printRow( int (*M)[COL], int row )

{

    int i;

    for( i = 0; i < COL; ++i )

        printf( "%d ", M[row][i] );

    printf("\n");

}

  
// Основная функция, которая печатает все уникальные строки в
// данная матрица.

void findUniqueRows( int (*M)[COL] )

{

    Node* root = NULL; // создаем пустой Trie

    int i;

  

    // Итерация по всем строкам

    for ( i = 0; i < ROW; ++i )

        // вставить строку в TRIE

        if ( insert(&root, M, i, 0) )

            // найдена уникальная строка, распечатать

            printRow( M, i );

}

  
// Программа драйвера для проверки вышеуказанных функций

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;

}


Выход:

0 1 0 0 1 
1 0 1 1 0 
1 0 1 0 0 

Временная сложность: O (ROW x COL)
Вспомогательное пространство: O (ROW x COL)

Этот метод имеет лучшую временную сложность. Также при печати поддерживается относительный порядок строк.

Метод 4 (Использовать структуру данных HashSet)
В этом методе преобразуйте всю строку в одну строку, а затем проверьте, присутствует ли она в HashSet или нет. Если строка присутствует, то мы оставим ее, в противном случае мы напечатаем уникальную строку и добавим ее в HashSet.
Спасибо, Anshuman Kaushik за предложенный метод.

C / C ++

// C ++ код для печати уникальной строки в
// заданная двоичная матрица
#include<bits/stdc++.h> 

using namespace std; 

  

void printArray(int arr[][5], int row, 

                              int col) 

    unordered_set<string> uset; 

      

    for(int i = 0; i < row; i++) 

    

        string s = ""

          

        for(int j = 0; j < col; j++) 

            s += to_string(arr[i][j]); 

          

        if(uset.count(s) == 0) 

        

            uset.insert(s); 

            cout << s << endl; 

              

        

    

  
// Код драйвера

int main()

    int arr[][5] = {{0, 1, 0, 0, 1}, 

                    {1, 0, 1, 1, 0}, 

                    {0, 1, 0, 0, 1}, 

                    {1, 1, 1, 0, 0}}; 

      

    printArray(arr, 4, 5); 

  
// Этот код предоставлен
// ратбхупендра

Джава

// Java-код для печати уникальной строки в
// заданная двоичная матрица

import java.util.HashSet;

  

public class GFG {

  

    public static void printArray(int arr[][], 

                               int row,int col)

    {

          

        HashSet<String> set = new HashSet<String>();

          

        for(int i = 0; i < row; i++)

        {

            String s = "";

              

            for(int j = 0; j < col; j++) 

                s += String.valueOf(arr[i][j]);

              

            if(!set.contains(s)) {

                set.add(s);

                System.out.println(s);

                  

            }

        }

    }

      

    // Код драйвера

    public static void main(String[] args) {

          

        int arr[][] = { {0, 1, 0, 0, 1},

                        {1, 0, 1, 1, 0},

                        {0, 1, 0, 0, 1},

                        {1, 1, 1, 0, 0} };

          

        printArray(arr, 4, 5);

    }

}

python3

# Python3 код для печати уникальной строки в
# заданная двоичная матрица

  

def printArray(matrix):

  

    rowCount = len(matrix)

    if rowCount == 0:

        return

  

    columnCount = len(matrix[0])

    if columnCount == 0:

        return

  

    row_output_format = " ".join(["%s"] * columnCount)

  

    printed = {}

  

    for row in matrix:

        routput = row_output_format % tuple(row)

        if routput not in printed:

            printed[routput] = True

            print(routput)

  
Код водителя

mat = [[0, 1, 0, 0, 1], 

       [1, 0, 1, 1, 0], 

       [0, 1, 0, 0, 1],

       [1, 1, 1, 0, 0]]

  
printArray(mat)

  
# Этот код предоставлен myronwalker

C #

using System;

using System.Collections.Generic;

  
// c # код для печати уникальной строки в
// заданная двоичная матрица

  

public class GFG

{

  

    public static void printArray(int[][] arr, int row, int col)

    {

  

        HashSet<string> set = new HashSet<string>();

  

        for (int i = 0; i < row; i++)

        {

            string s = "";

  

            for (int j = 0; j < col; j++)

            {

                s += arr[i][j].ToString();

            }

  

            if (!set.Contains(s))

            {

                set.Add(s);

                Console.WriteLine(s);

  

            }

        }

    }

  

    // Код драйвера

    public static void Main(string[] args)

    {

  

        int[][] arr = new int[][]

        {

            new int[] {0, 1, 0, 0, 1},

            new int[] {1, 0, 1, 1, 0},

            new int[] {0, 1, 0, 0, 1},

            new int[] {1, 1, 1, 0, 0}

        };

  

        printArray(arr, 4, 5);

    }

}

  
// Этот код предоставлен Shrikant13


Выход:

01001
10110
11100

Временная сложность: O (ROW x COL)
Вспомогательное пространство: O (ROW)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Печать уникальных строк в заданной логической матрице

0.00 (0%) 0 votes