数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济
心理学
社会学
时尚研究
法律研究使用 C++ 查找包含最大 1 数的
在此问题中，我们得到一个二进制矩阵，其中每一行的元素都是经过排序的。我们的任务是找到包含最多 1 数的行。
我们举一个例子来理解这个问题，
输入
mat[][] = {{ 0 1 1 1}
{1 1 1 1}
{0 0 0 1}
{0 0 1 1}}输出
1
说明
The count of 1’s in each row of the matrix : Row 0 : 3 Row 1 : 4 Row 2 : 1 Row 3 : 2
解决方案
一个简单的解决方案是通过查找第 1 个 1 的最小索引的行。
一种方法是使用按行遍历来找出第 1 个 1 的索引，这将返回该行中最多 1 的计数。然后我们将返回最大 1 计数的行。
另一种方法是使用二分查找在每一行中找到第 1 个 1 的出现。然后，我们将返回 1 最多的值。
举例
一个程序来说明我们解决方案的工作原理
#include <iostream>
using namespace std;
#define R 4
#define C 4
int findFirst1BinSearch(bool arr[], int low, int high){
if(high >= low){
int mid = low + (high - low)/2;
if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
return mid;
else if (arr[mid] == 0)
return findFirst1BinSearch(arr, (mid + 1), high);
else
return findFirst1BinSearch(arr, low, (mid -1));
}
return -1;
}
int findMaxOneRow(bool mat[R][C]){
int max1RowIndex = 0, max = -1;
for (int i = 0; i < R; i++){
int first1Index = findFirst1BinSearch(mat[i], 0, C-1);
if (first1Index != -1 && C-first1Index > max){
max = C - first1Index;
max1RowIndex = i;
}
}
return max1RowIndex;
}
int main(){
bool mat[R][C] = { {0, 1, 1, 1},
{1, 1, 1, 1},
{0, 0, 1, 1},
{0, 0, 0, 1}};
cout<<"The row with maximum number of 1's in the matrix is "<<findMaxOneRow(mat);
return 0;
}输出
The row with maximum number of 1's in the matrix is 1
更新于： 14-Feb-2022
243 次浏览
广告