在 C++ 中查找最大数为 1 的二进制矩阵的行号
在这个问题中，我们给出了一个二进制矩阵，其中每一行都被排序。我们的任务是找到最大数量为 1 的二进制矩阵的行号。
让我们举个例子来理解这个问题，
输入
binMat[][] = { 1, 1, 1, 1
0, 0, 0, 0
0, 0, 0, 1
0, 0, 1, 1
}
输出结果1
解决方法
该问题的一个简单解决方案是计算每行中 1 的总数。然后返回最大 1 个计数的行号。
程序来说明我们的解决方案的工作，
示例
#include <iostream>输出结果using namespace std;
#define R 4
#define C 4
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
int oneCount = 0;
for(int j = 0; j < C; j++){
if(mat[i][j])
oneCount++;
}
if(oneCount > max1Count){
max1Count = oneCount;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
}
最大 1 的行数是 1 一个更好的解决方案是对每一行使用二分搜索来找到该行中第一次出现的 1。可以使用行大小 - 第一个 1 的索引找到行中的数字 1。使用它，我们可以找到每行中 1 的数量，然后返回最大数量为 1 的行
程序来说明我们的解决方案的工作，
示例
#include <iostream>输出结果using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int max1Row = 0, max1Count = -1;
int i, index;
for (i = 0; i < R; i++) {
index = binarySearch1Row(mat[i], 0, C-1);
if (index != -1 && ( C-index) > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
}
The number of row with maximum number of 1's is 1
添加到上述方法的优化可以使用第一个 1 的索引检查当前行是否比前一行有更多的 1。如果它有更多的 1，则执行二分查找，但从 0 到最后一行的第一个 1 的索引。
这将节省计算比当前 1 少的 1 的行数的开销。
程序来说明我们的解决方案的工作，
示例
#include <iostream>输出结果using namespace std;
#define R 4
#define C 4
int binarySearch1Row(bool arr[], int start, int end) {
if(end >= start) {
int mid = start + (end - start)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return binarySearch1Row(arr, (mid + 1), end);
else
return binarySearch1Row(arr, start, (mid -1));
}
return -1;
}
int findMax1Row(bool mat[R][C]) {
int i, index;
int max1Row = 0;
int max1Count = binarySearch1Row(mat[0], 0, C - 1);
for (i = 1; i < R; i++){
if (max1Count != -1 && mat[i][C - max1Count - 1] == 1) {
index = binarySearch1Row (mat[i], 0, C - max1Count);
if (index != -1 && C - index > max1Count) {
max1Count = C - index;
max1Row = i;
}
}
else
max1Count = binarySearch1Row(mat[i], 0, C - 1);
}
return (max1Row + 1);
}
int main() {
bool mat[R][C] = {
{0, 1, 1, 1},
{0, 0, 0, 1},
{0, 0, 1, 1},
{0, 0, 0, 0}
};
cout<<"The number of row with maximum number of 1's is "<<findMax1Row(mat);
return 0;
}
The number of row with maximum number of 1's is 1
以上是 在 C++ 中查找最大数为 1 的二进制矩阵的行号 的全部内容， 来源链接： utcz.com/z/327575.html
