Java 中显示二进制矩阵中的唯一行

2025年3月17日 | 阅读 15 分钟

在本节中，我们将讨论如何在 Java 中显示二进制矩阵的唯一行。在此问题中，给出了一个二进制矩阵，我们需要识别并打印给定的二进制矩阵的唯一行。

示例 1

Display Unique Rows in a Binary Matrix in Java

解释

在上面的输入矩阵中，有 5 行

R1 = {0, 1, 1, 0, 0}，R2 = {1, 0, 0, 1, 1}，R3 = {0, 1, 1, 1, 1}，R4 = {0, 1, 1, 0, 0, 0}，以及

R5 = {0, 0, 1, 0, 1}。在这 5 行中，R1 和 R4 行相同，其余行是唯一的。因此，输出中舍弃了 R4 行。

示例 2

解释

在上面的输入矩阵中，有 4 行

R1 = {0, 1, 1, 0}，R2 = {1, 0, 1, 0}，R3 = {0, 1, 1, 0}，R4 = {1, 0, 0, 1}。在这 4 行中，R1 和 R3 行相同，其余行是唯一的。因此，输出中舍弃了 R3 行。

朴素方法

朴素方法很简单。首先，打印第一行，然后检查第二行是否与已打印的行（第一行）匹配。如果匹配，则丢弃第二行；否则，打印第二行。对于第三行，检查它是否与已打印的行（第一行和第二行）匹配。如果不匹配，则不打印第三行；否则，打印第三行。其他行也以相同的方式处理。

实现步骤

以下是实现朴素方法所需的步骤。

步骤 1：逐行遍历矩阵的元素。

步骤 2：对于当前行，检查它是否与任何前一行匹配。

步骤 3：如果当前行与前一行匹配，则不打印当前行。

步骤 4：否则，显示当前行。

让我们看看上述算法的实现。

文件名：UniqueRowsMatrix.java

public class UniqueRowsMatrix
{
// method that prints all
// unique rows in a given matrix.
public void printUniqueRows(int matrix[][], int row, int col)
{
    // Traverse through the matrix
    for(int j = 0; j < row; j++)
    {
        // isUnqiue will get only 
        // two values, one is 0, and 
        // other is 1. 0 means the
        // row is not unique, and 1
        // means the row is unique
        int isUnqiue = 0;
        // Check whether there is a same column
        // that is already displayed, i.e if jth and
        // ith column match.
        for(int i = 0; i < j; i++)
        {
            isUnqiue = 0; 
            for(int k = 0; k < col; k++)
            {
                if (matrix[j][k] != matrix[i][k])
                {
                    isUnqiue = 1;
                }
            }
            if (isUnqiue == 0)
                break;
        } 
        // If the row is unique
        // or it is the first row
        if (isUnqiue == 1 || j == 0)
        {
            // display the row
            for(int p = 0; p < col; p++)
            {
                System.out.print(matrix[j][p] + " ");
            }
            System.out.println();
        }
    }
}
// main method
public static void main(String argvs[])
{
//creating an object of the class UniqueRowsMatrix
UniqueRowsMatrix obj = new UniqueRowsMatrix();

// input binary matrix
int matrix[][] = { { 0, 1, 1, 0, 0 },
                  { 1, 0, 0, 1, 1 },
                  { 0, 1, 1, 1, 1 },
                  { 0, 1, 1, 0, 0 },
                  { 0, 0, 1, 0, 1 }
                };
 
// row length of the matrix          
int row = matrix.length;

// column length of the matrix
int col = matrix[0].length;
System.out.println("For the following matrix: ");
for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println("The unique rows are: ");
obj.printUniqueRows(matrix, row, col);
System.out.println("\n");
// input binary matrix
int matrix1[][] = { { 0, 1, 1, 0 },
                  { 1, 0, 1, 0 },
                  { 0, 1, 1, 0 },
                  { 1, 0, 0, 1 }
                };
// row length of the matrix          
row = matrix1.length;
// column length of the matrix
col = matrix1[0].length;
System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}
System.out.println();
System.out.println("The unique rows are: ");
obj.printUniqueRows(matrix1, row, col);
 }
}

输出

For the following matrix: 
0 1 1 0 0 
1 0 0 1 1 
0 1 1 1 1 
0 1 1 0 0 
0 0 1 0 1 

The unique rows are: 
0 1 1 0 0 
1 0 0 1 1 
0 1 1 1 1 
0 0 1 0 1 

For the following matrix: 
0 1 1 0 
1 0 1 0 
0 1 1 0 
1 0 0 1 

The unique rows are: 
0 1 1 0 
1 0 1 0 
1 0 0 1

复杂度分析：在上面的程序中，我们将每一行与之前出现的行进行比较，以检查该行是否唯一。在行比较中，我们需要检查一行中的每个元素是否与另一行（列大小）匹配。因此，上述程序的 time complexity 为 O(R² x C)，其中 R 是矩阵中的总行数，C 是矩阵中的总列数。由于我们没有在程序中使用任何辅助数组，因此程序的 space complexity 是常数，即 O(1)。

如果我们观察上述程序，我们会发现有许多子问题被计算了不止一次，导致了指数级的时间复杂度。观察以下内容。

方法：使用二叉搜索树

在此方法中，第一个要求是计算每一行的十进制等效值，并将它们推入二叉搜索树。请注意，二叉搜索树的每个节点包含两个字段：一个用于十进制值，另一个用于行号。

实现步骤

以下是实现二叉搜索树方法所需的步骤。

步骤 1：创建一个不存储重复节点的二叉搜索树。

步骤 2：创建一个方法，将一行转换为十进制，并将十进制值转换为二进制数组。

步骤 3：遍历输入矩阵，并将行插入二叉搜索树。

步骤 4：对二叉搜索树进行中序遍历，将十进制转换为二进制数组，然后显示它。

让我们看看上述算法的实现。

文件名：UniqueRowsMatrix1.java

import java.util.*;
public class UniqueRowsMatrix1
{

  static class BST 
  {
    int val;
    BST lt, rt;
    BST(int val)
    {
      this.val = val;
      this.lt = this.rt = null;
    }
  }


  // converting array to decimal
  static int convertArr(int a[], int C)
  {
    int s = 0;
 
    for(int j = 0; j < C; j++)
    {
      s += Math.pow(2, j) * a[j];
    }
    
    return s;
  }
 
  // printing the column which is represented as the integers
  static void display(int p, int C)
  {
    for(int j = 0; j < C; j++)
    {
      System.out.print(p % 2 + " ");
      p = p / 2;
    }
    System.out.println();
  }
 
 
 
  // method that defines the insert.
  static BST Insert(BST rt, int val)
  {
    if(rt == null)
    {
      // Inserting the first node, if the root is null.
      return new BST(val);
    }
 
    //if the value is current
    if(val == rt.val)
    {
      return rt;
    }
 
    // Inserting the data.
    if(val > rt.val)
    {
      // Inserting the right node, if the 'value' that
      // has to be inserted is more than the 'rt' node value.
 
      // Processing the right nodes.
      rt.rt = Insert(rt.rt, val);
    }
    else
    {
      // Inserting the left node data, if the 'val' that
      // has to be inserted is more than the 'rt' node value.
 
      // Processing the left nodes.
      rt.lt = Insert(rt.lt, val);
    }
 
    // Returning 'rt' node, after the insertion.
    return rt;
  }
 
  // Inorder traversal of the BST.
  // It gives the data in sorted order.
  static void Inorder(BST rt, int C)
  {
    if(rt == null)
    {
      return;
    }
    Inorder(rt.lt, C);
    display( rt.val, C );
    Inorder(rt.rt, C);
  }
 
  // The main method that display
  // all the unique rows in the given matrix.
  static void printUniqueRows(int matrix[][], int R, int C)
  {
 
    BST b, rt = null;
 
    // Traversing the matrix
    for(int j = 0; j < R; j++)
    {
      // inserting the row into the BST
      rt = Insert(rt, convertArr(matrix[j], C));
    }
 
 
    //print
    Inorder(rt, C);
 
  }


// main method
public static void main(String argvs[])
{
//creating an object of the class UniqueRowsMatrix1
UniqueRowsMatrix1 obj = new UniqueRowsMatrix1();

// input binary matrix
int maxtrix[][] = { { 0, 1, 1, 0, 0 },
                  { 1, 0, 0, 1, 1 },
                  { 0, 1, 1, 1, 1 },
                  { 0, 1, 1, 0, 0 },
                  { 0, 0, 1, 0, 1 }
                };
 
// row length of the matrix          
int row = maxtrix.length;

// column length of the matrix
int col = maxtrix[0].length;


System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(maxtrix[i][j] + " ");
}
System.out.println();
}

System.out.println();
System.out.println("The unique rows are: ");
obj.printUniqueRows(maxtrix, row, col);
 
System.out.println("\n");


// input binary matrix
int matrix1[][] = { { 0, 1, 1, 0 },
                  { 1, 0, 1, 0 },
                  { 0, 1, 1, 0 },
                  { 1, 0, 0, 1 }
                };
 
// row length of the matrix          
row = matrix1.length;

// column length of the matrix
col = matrix1[0].length;


System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}

System.out.println();
System.out.println("The unique rows are: ");
obj.printUniqueRows(matrix1, row, col);
 


}
}

输出

For the following matrix: 
0 1 1 0 0 
1 0 0 1 1 
0 1 1 1 1 
0 1 1 0 0 
0 0 1 0 1 

The unique rows are: 
0 1 1 0 0 
0 0 1 0 1 
1 0 0 1 1 
0 1 1 1 1

For the following matrix: 
0 1 1 0 
1 0 1 0 
0 1 1 0 
1 0 0 1 

The unique rows are: 
0 1 1 0 
1 0 1 0 
1 0 0 1

复杂度分析：在上面的程序中，我们遍历矩阵的每一行和每一列，time complexity 为 O(R * C)。另外，在二叉搜索树中插入一行的 time complexity 为 O(R)。由于我们插入每一行，因此插入消耗的时间为 R * O(log(R))。因此，上述程序的 overall time complexity 为 O(R * C + R * (log(R)))。在程序中，我们使用辅助空间来存储二叉搜索数组，导致 space complexity 为 O(R)，其中 R 是输入矩阵的行大小，C 是输入矩阵的列大小。

方法：使用 TRIE

在此方法中，我们将使用 TRIE 数据结构来查找唯一行。我们知道 TRIE 数据结构是一种高效的数据检索数据结构。使用 TRIE 数据结构，可以优化搜索的复杂性。我们知道输入矩阵是二进制矩阵；因此，我们将对 TRIE 数据结构进行一些定制，其中每个节点将有两个子节点，一个用于 1，另一个用于 0。

实现步骤

步骤 1：创建一个 TRIE 数据结构来存储行。

步骤 2：遍历每一行，并将其插入到上一步创建的 TRIE 数据结构中。由于 TRIE 永远不能包含任何重复条目；因此，当我们遍历重复行以将其插入 TRIE 时；它不会影响 TRIE 数据结构。因此，在遍历完输入矩阵的每一行后，TRIE 中存在的都是唯一行。

步骤 3：遍历 TRIE 数据结构并显示行。

让我们看看上述算法的实现。

文件名：UniqueRowsMatrix2.java

// An implementation of the insert and search operations
// on the Trie Data structure
public class UniqueRowsMatrix2 {
	
	// The count is 2 as we are dealing in 1's and 2's
	static final int CNT = 2;
	
	// trie node
	static class TNode
	{
		TNode[] children = new TNode[CNT];
	
		// isEndOfRow is true if and only if the node represents
		// the end of the row
		boolean isEndOfRow;
		
		TNode(){
			isEndOfRow = false;
			for (int j = 0; j < CNT; j++)
				children[j] = null;
		}
	};
	
	static TNode rt;
	
	// If not present, inserts key into trie
	// If the key is prefix of trie node,
	// just marks leaf node
	static boolean insert(int row[])
	{
		int lvl;
		int size = row.length;
		int idx;

		TNode pCrawl = rt;
		
		boolean isUnique = false;
	
	    // from every node we have the two options to follow
	    // one to follow the 1's and the other is to 
	    // follow the 0's. What we are going to follow 
	    // is decided by the number present in the row[] array
		for (lvl = 0; lvl < size; lvl++)
		{
		    // idx will be always 0 and 1
			idx = row[lvl];
			
			
			// it is this if block that makes the TRIE to 
			// discard the redundant rows
			
			// the if block checks whether the path has been 
			// traversed earlier or not. If yes, then no any new
			// node is created. If not traversed, then a new node is created
			if (pCrawl.children[idx] == null)
			{
				pCrawl.children[idx] = new TNode();
				isUnique = true;
			}
	
			pCrawl = pCrawl.children[idx];
		}
	
		// marking the last node as the leaf node
		pCrawl.isEndOfRow = true;
		
		return isUnique;
	}
	
	// A utility method for displaying the unique rows
    void displayRow(int input[][], int row)
    {
        int j;
        int colSize = input[0].length;
        for(j = 0; j < colSize; ++j)
        {
            System.out.print(input[row][j] + " ");
        }
        System.out.println();
    }
    
    
    
    // it is the method that is being invoked
    // by the main() method. The method filters out the unique 
    // rows from the input matrix and displays it by invoking the 
    // displayRow() method
    void filterAndPrintUniqueRows(int input[][], int R, int C)
    {
        rt = new TNode(); // creating an empty Trie
        int j;
     
        // Iterating through all of the rows
        for (j = 0; j < R; ++j)
         
            // inserting row into the TRIE
            if (insert(input[j]))
            {
                // a unique row is found, display it
                displayRow(input, j);
            }
    }
	
	// main method
public static void main(String argvs[])
{
//creating an object of the class UniqueRowsMatrix2
UniqueRowsMatrix2 obj = new UniqueRowsMatrix2();

// input binary matrix
int maxtrix[][] = { { 0, 1, 1, 0, 0 },
                  { 1, 0, 0, 1, 1 },
                  { 0, 1, 1, 1, 1 },
                  { 0, 1, 1, 0, 0 },
                  { 0, 0, 1, 0, 1 }
                };
 
// row length of the matrix          
int row = maxtrix.length;

// column length of the matrix
int col = maxtrix[0].length;


System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(maxtrix[i][j] + " ");
}
System.out.println();
}

System.out.println();
System.out.println("The unique rows are: ");
obj.filterAndPrintUniqueRows(maxtrix, row, col);
 
System.out.println("\n");


// input binary matrix
int matrix1[][] = { { 0, 1, 1, 0 },
                  { 1, 0, 1, 0 },
                  { 0, 1, 1, 0 },
                  { 1, 0, 0, 1 }
                };
 
// row length of the matrix          
row = matrix1.length;

// column length of the matrix
col = matrix1[0].length;


System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}

System.out.println();
System.out.println("The unique rows are: ");
obj.filterAndPrintUniqueRows(matrix1, row, col);
 


}
}

输出

For the following matrix: 
0 1 1 0 0 
1 0 0 1 1 
0 1 1 1 1 
0 1 1 0 0 
0 0 1 0 1 

The unique rows are: 
0 1 1 0 0 
0 0 1 0 1 
1 0 0 1 1 
0 1 1 1 1

For the following matrix: 
0 1 1 0 
1 0 1 0 
0 1 1 0 
1 0 0 1 

The unique rows are: 
0 1 1 0 
1 0 1 0 
1 0 0 1

复杂度分析：在上面的程序中，我们遍历矩阵的每一行和每一列，time complexity 为 O(R * C)。在程序中，我们使用辅助空间来存储 TRIE 数据结构，导致 space complexity 为 O(R * C)，其中 R 是输入矩阵的行大小，C 是输入矩阵的列大小。

方法：使用 HashSet

在此方法中，我们将使用 HashSet 数据结构来查找唯一行。我们知道 HashSet 数据结构实现了 Set 接口。因此，HashSet 中不能存在任何重复数据。该方法是将 HashSet 的每一行转换为 String 并将其插入 HashSet。

实现步骤

步骤 1：创建一个 HashSet 数据结构来存储行。

步骤 2：遍历每一行，并将其插入到上一步创建的 Hash 数据结构中。由于 HashSet 永远不能包含任何重复条目；因此，当我们遍历重复行以将其插入 HashSet 时，它不会影响 HashSet 数据结构。因此，在遍历完输入矩阵的每一行后，HashSet 中存在的都是唯一行。请注意，在将行插入 HashSet 之前，将其转换为 String。例如，

对于以下行

我们将得到字符串“10011”。

步骤 3：遍历 HashSet 数据结构并显示行。

让我们看看上述算法的实现。

文件名：UniqueRowsMatrix3.java

// importing inbuilt HashSet
import java.util.HashSet;

public class UniqueRowsMatrix3 {
	
    public void filterAndPrintUniqueRows(int input[][], int R, int C)
    {
        // creating an obejct of the HashSet class
        HashSet<String> hs = new HashSet<String>();
         
        for(int j = 0; j < R; j++)
        {
            // for stroing the string generated from the row
            // of the input matrix
            String str = "";
             
             
            // loop for converting the row into a string 
            for(int i = 0; i < C; i++)
            {
                str = str + String.valueOf(input[j][i]);
            }
            
            
            if(!hs.contains(str)) 
            {
                hs.add(str);
                
                int size = str.length();
                
                // displaying the unique row
                for(int i = 0; i < size; i++)
                {
                    System.out.print(str.charAt(i) + " ");
                }
                
                System.out.println();
                 
            }
        }
    }
	
	// main method
public static void main(String argvs[])
{
//creating an object of the class UniqueRowsMatrix3
UniqueRowsMatrix3 obj = new UniqueRowsMatrix3();

// input binary matrix
int maxtrix[][] = { { 0, 1, 1, 0, 0 },
                  { 1, 0, 0, 1, 1 },
                  { 0, 1, 1, 1, 1 },
                  { 0, 1, 1, 0, 0 },
                  { 0, 0, 1, 0, 1 }
                };
 
// row length of the matrix          
int row = maxtrix.length;

// column length of the matrix
int col = maxtrix[0].length;


System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(maxtrix[i][j] + " ");
}
System.out.println();
}

System.out.println();
System.out.println("The unique rows are: ");
obj.filterAndPrintUniqueRows(maxtrix, row, col);
 
System.out.println("\n");


// input binary matrix
int matrix1[][] = { { 0, 1, 1, 0 },
                  { 1, 0, 1, 0 },
                  { 0, 1, 1, 0 },
                  { 1, 0, 0, 1 }
                };
 
// row length of the matrix          
row = matrix1.length;

// column length of the matrix
col = matrix1[0].length;


System.out.println("For the following matrix: ");

for(int i = 0; i < row; i++)
{
for(int j = 0; j < col; j++)
{
System.out.print(matrix1[i][j] + " ");
}
System.out.println();
}

System.out.println();
System.out.println("The unique rows are: ");
obj.filterAndPrintUniqueRows(matrix1, row, col);
 


}
}

输出

For the following matrix: 
0 1 1 0 0 
1 0 0 1 1 
0 1 1 1 1 
0 1 1 0 0 
0 0 1 0 1 

The unique rows are: 
0 1 1 0 0 
0 0 1 0 1 
1 0 0 1 1 
0 1 1 1 1

For the following matrix: 
0 1 1 0 
1 0 1 0 
0 1 1 0 
1 0 0 1 

The unique rows are: 
0 1 1 0 
1 0 1 0 
1 0 0 1

复杂度分析：在上面的程序中，我们遍历矩阵的每一行和每一列，time complexity 为 O(R * C)。在程序中，我们使用辅助空间来存储 Hash 数据结构，导致 space complexity 为 O(R * C)，其中 R 是输入矩阵的行大小，C 是输入矩阵的列大小。

下一个主题Java 中将矩阵旋转 180 度

← 上一个下一个 →

Java 中显示二进制矩阵中的唯一行

朴素方法

实现步骤

方法：使用二叉搜索树

实现步骤

方法：使用 TRIE

实现步骤

方法：使用 HashSet

实现步骤

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Java 中显示二进制矩阵中的唯一行

朴素方法

实现步骤

方法：使用二叉搜索树

实现步骤

方法：使用 TRIE

实现步骤

方法：使用 HashSet

实现步骤

相关帖子

检查给定字符串是否为偶奇回文（Java）

Matrix Exponential ion Java

Java 中的窗口事件

Java 中二叉树的底视图

Java 中的数字级数程序

Java 和 JDK 的区别

使用 Java 泛型在竞争性编程中高效编码

DoubleBuffer equals() method in Java with Examples

Java 中的调和数

Java 退出码 13

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器