資料結構
網路
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 次檢視
廣告