查找包含最多 1 的行

给定一个布尔二维数组，其中每一行都按升序排序。我们的任务是找到值为 true（也称为 1）数量最多的行，并返回该行的索引。

示例 1

输入

输出

1

示例 2

输入

输出

2

方法：逐行遍历

逐行遍历是矩阵相关问题中常用的一种方法，即一次遍历矩阵的一行。在这种方法中，我们遍历矩阵的每一行，并在移动到下一行之前对每个元素执行一些操作。当矩阵的行数很多但列数很少时，此技术尤其有用，因为它可以最大程度地减少所需的列向操作次数。

文件名： MaxOnesRowFinder.java

输出

Max row index: 2

复杂度分析： MaxOnesRowFinder 类中 findMaxRow 方法的时间复杂度为 O(m*n)，其中 m 是输入矩阵的行数，n 是列数。这是因为该方法遍历每一行，然后遍历该行中的每个元素以计算 1 的数量。countOnes 方法由 findMaxRow 调用，其时间复杂度为 O(n)，其中 n 是输入行中的元素数量。

MaxOnesRowFinder 类的空间复杂度为 O(1)，因为该算法仅使用固定数量的变量来跟踪具有最多 1 的行以及该行中 1 的数量。输入矩阵未被修改，也没有创建其他数据结构。因此，空间复杂度不取决于输入矩阵的大小。

方法：二分查找

二分查找方法用于查找二元矩阵中 1 的数量最多的行，该方法涉及遍历每一行并使用二分查找计算每一行中 1 的数量。该算法维护两个变量来跟踪迄今为止看到的 1 的最大计数以及相应的行索引。它应用二分查找技术来有效地计算给定行中 1 的数量。

算法

步骤 1：定义一个公共类 BinaryMatrixRowWithMax1s。

步骤 2：定义一个公共方法 rowWithMax1s(int[][] mat) 来查找二元矩阵中 1 的数量最多的行。此方法应接受一个整数二维数组作为输入。

步骤 3：初始化变量来存储具有最多 1 的行的行索引和最多 1 的数量。

步骤 4：遍历矩阵的每一行，并使用二分查找计算当前行中 1 的数量。如果当前计数超过最大计数，则更新最大计数和相应的行索引。

步骤 5：返回具有最多 1 的行的行索引。

实施

文件名： BinaryMatrixRowWithMax1s.java

输出

Row with maximum 1s: 2

复杂度分析

BinaryMatrixRowWithMax1s 方法的时间复杂度为 O(m*logn)，其中 m 是输入矩阵的行数，n 是列数。这是因为该方法遍历每一行，并在每一行上执行二分查找以计算 1 的数量，这在最坏情况下需要 logn 时间。countOnes 方法的时间复杂度也为 O(logn)，因为它对单行执行二分查找以计算 1 的数量。

代码的空间复杂度为 O(1)，因为唯一使用的额外空间是用于存储最大行索引和最多 1 的数量，它们都是整数。代码执行期间未修改输入矩阵。