Encuentra filas duplicadas en una array binaria

Dada una array binaria cuyos elementos son solo 0 y 1, necesitamos imprimir las filas que son duplicados de las filas que ya están presentes en la array.

Ejemplos: 

Input : {1, 1, 0, 1, 0, 1},
    {0, 0, 1, 0, 0, 1},
    {1, 0, 1, 1, 0, 0},
    {1, 1, 0, 1, 0, 1},
    {0, 0, 1, 0, 0, 1},
    {0, 0, 1, 0, 0, 1}.

Output :
There is a duplicate row at position: 4 
There is a duplicate row at position: 5 
There is a duplicate row at position: 6 

Este problema es principalmente una extensión de encontrar filas únicas en una array binaria .

Una solución simple es recorrer todas las filas una por una. Para cada fila, verifique si está presente en algún otro lugar. En caso afirmativo, imprima la fila. 

• Complejidad de tiempo: O (FILA ^ 2 x COL) 
• Espacio Auxiliar : O(1)

Solución óptima usando Trie Trie es una estructura de datos eficiente usada para almacenar y recuperar datos donde el conjunto de caracteres es pequeño. La complejidad de búsqueda es óptima como longitud de clave. 

El enfoque de solución a la pregunta es insertar primero la array en el trie binario y luego, si la nueva fila agregada ya está presente en el trie, ahora sabremos que es una fila duplicada 

Implementación:

// C++ program to find duplicate rows
// in a binary matrix.
#include<bits/stdc++.h>
 
const int MAX = 100;
 
/*struct the Trie*/
struct Trie
{
    bool leaf;
    Trie* children[2];
};
 
/*function to get Trienode*/
Trie* getNewTrieNode()
{
    Trie* node = new Trie;
    node->children[0] = node->children[1] = NULL;
    node->leaf = false;
    return node;
}
 
/* function to insert a row in Trie*/
bool insert(Trie*& head, bool* arr, int N)
{
    Trie* curr = head;
 
    for (int i = 0; i < N; i++)
    {
        /*creating a new path if it don not exist*/
        if (curr->children[arr[i]] == NULL)
            curr->children[arr[i]] = getNewTrieNode();
 
        curr = curr->children[arr[i]];
    }
 
    /*if the row already exist return false*/
    if (curr->leaf)
        return false;
 
    /* making leaf node tree and return true*/
    return (curr->leaf = true);
}
 
void printDuplicateRows(bool mat[][MAX], int M, int N)
{
    Trie* head = getNewTrieNode();
 
    /*inserting into Trie and checking for duplicates*/
    for (int i = 0; i < M; i++)
 
        // If already exists
        if (!insert(head, mat[i], N))
            printf("There is a duplicate row"
                  " at position: %d \n", i+1);
 
}
 
/*driver function to check*/
int main()
{
    bool mat[][MAX] =
    {
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {0, 0, 1, 0, 0, 1},
    };
 
    printDuplicateRows(mat, 6, 6);
    return 0;
}

There is a duplicate row at position: 4 
There is a duplicate row at position: 5 
There is a duplicate row at position: 6 

Otro enfoque sin usar Trie pero no funciona para una gran cantidad de columnas 
. Otro enfoque es convertir el equivalente decimal de la fila y verificar si una nueva fila tiene el mismo equivalente decimal, entonces es una fila duplicada. No funcionará si el número de columnas es grande.

Aquí está la implementación del enfoque anterior.

#include<iostream>
#include<vector>
#include<set>
using namespace std;
vector<int> repeatedRows(vector<vector<int>> matrix, int M, int N)
{
     
    set<int>s;
     
    // vector to store the repeated rows
    vector<int>res;
     
    for(int i=0;i<M;i++){
        // calculating decimal equivalent of the row
        int no=0;
        for(int j=0;j<N;j++){
            no+=(matrix[i][j]<<j);
        }
         
        /*
        rows with same decimal equivalent will be same,
        therefore, checking through set if the calculated equivalent was
        present before;
        if yes then add to the result otherwise insert in the set
        */
        if(s.find(no)!=s.end()){
            res.push_back(i);
        }
        else{
            s.insert(no);
        }
    }
     
    return res;
   
}
int main() {
 
  vector<vector<int>>matrix={
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 0, 0},
        {1, 1, 0, 1, 0, 1},
        {0, 0, 1, 0, 0, 1},
        {0, 0, 1, 0, 0, 1},};
     
  int m=matrix.size();
  int n=matrix[0].size();
  vector<int>res=repeatedRows(matrix,m,n);
  for(int e:res){
     cout<< "There is a duplicate row at position: "<<e+1 << '\n';
  }
     
   
    return 0;
}

/*package whatever //do not write package name here */
 
import java.io.*;
import java.util.*;
 
class GFG {
  static ArrayList<Integer> repeatedRows(int[][] matrix, int M, int N)
  {
 
    TreeSet<Integer> s = new TreeSet<>();
 
    // vector to store the repeated rows
    ArrayList<Integer> res = new ArrayList<>();
 
    for(int i = 0; i < M; i++)
    {
       
      // calculating decimal equivalent of the row
      int no = 0;
      for(int j = 0; j < N; j++)
      {
        no+=(matrix[i][j]<<j);
      }
 
      /*
            rows with same decimal equivalent will be same,
            therefore, checking through set if the calculated equivalent was
            present before;
            if yes then add to the result otherwise insert in the set
            */
      if(s.contains(no)){
        res.add(i);
      }
      else{
        s.add(no);
      }
    }
 
    return res;
 
  }
 
  // Driver Code
  public static void main(String args[])
  {
    int[][] matrix={
      {1, 1, 0, 1, 0, 1},
      {0, 0, 1, 0, 0, 1},
      {1, 0, 1, 1, 0, 0},
      {1, 1, 0, 1, 0, 1},
      {0, 0, 1, 0, 0, 1},
      {0, 0, 1, 0, 0, 1}
    };
 
    int m = matrix.length;
    int n = matrix[0].length;
    ArrayList<Integer> res = repeatedRows(matrix,m,n);
    for(int e:res){
      System.out.println("There is a duplicate row at position: "+(e+1));
    }
  }
}
 
// This code is contributed by shinjanpatra

def repeatedRows(matrix, M, N):
 
    s = set()
     
    # vector to store the repeated rows
    res = []
     
    for i in range(M):
        # calculating decimal equivalent of the row
        no = 0
        for j in range(N):
            no += (matrix[i][j] << j)
         
        # rows with same decimal equivalent will be same,
        # therefore, checking through set if the calculated equivalent was
        # present before
        # if yes then add to the result otherwise insert in the set
         
        if(no in s):
            res.append(i)
         
        else:
            s.add(no)
     
    return res
 
# driver code
matrix = [
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1],
    [0, 0, 1, 0, 0, 1]
]
     
m = len(matrix)
n = len(matrix[0])
res = repeatedRows(matrix,m,n)
for e in res:
   print("There is a duplicate row at position: "+str(e+1))
 
# This code is contributed by shinjanpatra

<script>
 
function repeatedRows(matrix,M,N)
{
     
    let s = new Set();
     
    // vector to store the repeated rows
    let res = [];
     
    for(let i=0;i<M;i++){
        // calculating decimal equivalent of the row
        let no=0;
        for(let j=0;j<N;j++){
            no+=(matrix[i][j]<<j);
        }
         
        /*
        rows with same decimal equivalent will be same,
        therefore, checking through set if the calculated equivalent was
        present before;
        if yes then add to the result otherwise insert in the set
        */
        if(s.has(no)){
            res.push(i);
        }
        else{
            s.add(no);
        }
    }
     
    return res;
   
}
 
// driver code
 
let matrix = [
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1],
    [1, 0, 1, 1, 0, 0],
    [1, 1, 0, 1, 0, 1],
    [0, 0, 1, 0, 0, 1],
    [0, 0, 1, 0, 0, 1]
];
     
let m = matrix.length;
let n = matrix[0].length;
let res = repeatedRows(matrix,m,n);
for(let e of res){
   document.write("There is a duplicate row at position: "+(e+1),"</br>");
}
 
// This code is contributed by shinjanpatra
 
</script>

There is a duplicate row at position: 4
There is a duplicate row at position: 5
There is a duplicate row at position: 6

Complejidad de tiempo=O(M*N)
Complejidad de espacio=O(M)  donde M es el número de filas

Este artículo es una contribución de Pranav . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.