数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究在 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
更新于: 2021-03-16
127 次查看
广告