数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究打印给定二进制矩阵中的唯一行
在计算机科学中，二进制矩阵占据着非常重要的地位，包含大量信息，因为数据是使用 0 和 1 来表示的，这是计算机的语言。在二进制矩阵中，唯一行指的是与矩阵中任何其他行都不相同的行。每行唯一行包含唯一的信息，这些信息在矩阵中的其他任何地方都不存在，除了该行本身。发现这些唯一行可以提供有关行之间关系、矩阵中的模式以及关键元素识别方面的信息。
问题陈述
给定一个包含 0 和 1 的二进制矩阵 mat[]。任务是打印矩阵的所有唯一行。
示例 1
输入
mat[][] =
{{1, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1}}
输出
1 0 1 1 0 0 1 0 0 0 0 1 0 0 1
解释
In the given matrix, row1 = 1 0 1 1 0 row2 = 0 1 0 0 0 row3 = 1 0 1 1 0 row4 = 0 1 0 0 1 Since, row1 = row3 so unique rows are row1, row2 and row4.
示例 2
输入
mat[][] =
{{1, 0, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 0, 1, 1, 0},
{1, 0, 1, 1, 0}}
输出
1 0 1 1 0
解释
In the given matrix, row1 = 1 0 1 1 0 row2 = 1 0 1 1 0 row3 = 1 0 1 1 0 row4 = 1 0 1 1 01
由于所有行都相等，因此唯一行是第 1 行。
方法 1：蛮力方法
该问题的蛮力解决方案是首先打印矩阵的第一行，然后对于每一行，检查前面的行以检查是否存在重复。
伪代码
function uniqueRows(mat: boolean[row][col], i: integer) -> boolean
flag <- false
for j from 0 to i - 1
flag <- true
for k from 0 to col
if mat[i][k] ≠ mat[j][k]
flag <- false
exit loop
if flag = true
break loop
return flag
示例：C++ 实现
以下代码打印二进制矩阵中的唯一行。
#include <bits/stdc++.h>
using namespace std;
#define row 4
#define col 5
// Function used to determine if a row is unique or not
bool uniqueRows(bool mat[row][col], int i){
bool flag = 0;
for (int j = 0; j < i; j++){
flag = 1;
for (int k = 0; k <= col; k++)
if (mat[i][k] != mat[j][k])
flag = 0;
if (flag == 1)
break;
}
return flag;
}
int main(){
bool mat[row][col] = {{1, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1}};
for (int i = 0; i < row; i++) {
if (!uniqueRows(mat, i)) {
for (int j = 0; j < col; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
}
return 0;
}
输出
1 0 1 1 0 0 1 0 0 0 0 1 0 0 1
时间复杂度 - O(col * row^2)
空间复杂度 - O(1)
方法 2：使用 Trie
使用 Trie 数据结构的方法是将每一行插入到具有 2 个字母大小的 Trie 中。如果之前见过该行，则不打印它，否则打印新唯一行。
伪代码
struct Trie
leaf: boolean
c: array of Trie pointers
function newNode() -> Trie pointer
node <- new Trie
node.c <- array of Trie pointers with size 2
node.c[0] <- null
node.c[1] <- null
node.leaf <- false
return node
function insert(head: reference to Trie pointer, arr: array of booleans) -> boolean
ptr <- head
for i from 0 to col - 1
if ptr.c[arr[i]] = null
ptr.c[arr[i]] <- newNode()
ptr <- ptr.c[arr[i]]
if ptr.leaf = true
return false
ptr.leaf <- true
return true
示例：C++ 实现
以下代码打印二进制矩阵中的唯一行。
#include <iostream>
using namespace std;
#define row 4
#define col 5
// Structure of trie
struct Trie {
bool leaf;
Trie *c[2];
};
// function to create new trie node
Trie *newNode(){
Trie *node = new Trie;
node->c[0] = node->c[1] = nullptr;
node->leaf = false;
return node;
}
// Function to insert elements of matrix to trie
bool insert(Trie *&head, bool *arr){
Trie *ptr = head;
for (int i = 0; i < col; i++) {
if (ptr->c[arr[i]] == nullptr) {
ptr->c[arr[i]] = newNode();
}
ptr = ptr->c[arr[i]];
}
// row inserted before
if (ptr->leaf) {
return false;
}
// new unique row; mark leaf node
return ptr->leaf = true;
}
int main(){
bool mat[row][col] = {{1, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1}};
Trie *head = newNode();
for (int i = 0; i < row; i++) {
if (insert(head, mat[i])) {
for (int j = 0; j < col; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
}
return 0;
}
输出
1 0 1 1 0 0 1 0 0 0 0 1 0 0 1
时间复杂度 - O(col * row)
空间复杂度 - O(col * row)
方法 3：十进制
该方法是将输入矩阵中的每一行转换为十进制数。我们手头剩下的任务将是比较所有十进制数并删除所有重复项并打印唯一对。
伪代码
function uniqueRow(mat: boolean[row][col], i: integer, set: unordered_set of integers) -> boolean
decimal <- 0
flag <- false
for j from 0 to col - 1
decimal <- decimal + mat[i][j] * 2^j
if decimal is in set
flag <- false
else
flag <- true
insert decimal into set
return flag
示例：C++ 实现
以下代码打印二进制矩阵中的唯一行。
#include <iostream>
#include <vector>
#include <unordered_set>
#include <cmath>
using namespace std;
#define row 4
#define col 5
// Function to find the unique row in the matrix
bool uniqueRow(bool mat[row][col], int i, unordered_set<unsigned> &set){
unsigned decimal = 0;
bool flag;
for (int j = 0; j < col; j++){
// Decimal equivalent
decimal += mat[i][j] * pow(2, j);
}
// Duplicate row
if (set.find(decimal) != set.end()){
flag = 0;
}
// Unique row
else {
flag = 1;
set.insert(decimal);
}
return flag;
}
int main() {
bool mat[row][col] = {{1, 0, 1, 1, 0},
{0, 1, 0, 0, 0},
{1, 0, 1, 1, 0},
{0, 1, 0, 0, 1}};
unordered_set<unsigned> set;
for (int i = 0; i < row; i++) {
if (uniqueRow(mat, i, set)) {
for (int j = 0; j < col; j++) {
cout << mat[i][j] << " ";
}
cout << endl;
}
}
return 0;
}
输出
1 0 1 1 0 0 1 0 0 0 0 1 0 0 1
时间复杂度 - O(col * row)
空间复杂度 - O(col)
结论
总之，给定的解决方案和代码提供了有效的解决方案来识别和打印二进制矩阵中的唯一行。此问题在数据分析和模式识别等领域具有实际应用。
更新于： 2023-11-03
444 次查看
广告