Python 程序查找包含最多 1 的行

在本教程中，我们将编写一个 Python 程序来查找给定二维矩阵中 1 最多的行。在给定的矩阵中，每一行都是排序的，我们需要找到包含最多 1 的行。让我们看下面的例子。

示例 -

输入矩阵

输出

2

解释 -

第二行包含最多的 1。

让我们来解决这个问题。

解决方案

一种简单的方法是遍历给定矩阵中的每一行，计算 1 的数量并与最大值进行比较。一旦我们得到最多的 1，就返回该索引。我们将使用二分查找算法来解决这个问题。让我们理解下面的例子。

示例 -

输出

Index of row with maximum 1s is: 2

解释 -

在上面的代码中，我们首先定义了 find_first_one() 函数，这是一个递归二分查找算法。它接受一个排序的布尔数组 (arr) 以及定义搜索范围的低位和高位索引。它使用分而治之的方法递归搜索数组中第一个 1 的索引。如果找到 1，它将返回索引；否则，它会在数组的适当一侧继续搜索。

然后，find_row_with_max_ones() 函数遍历给定矩阵的每一行。对于每一行，它调用 find_first_one() 函数来查找该行中第一个 1 的索引。它跟踪具有最多 1 的行的索引 (max_row_index) 以及该行中 1 的数量 (max_count)。如果一行中的 1 比之前找到的最大值多，它会相应地更新 max_row_index 和 max_count。最后，find_row_with_max_ones 函数返回 max_row_index，它代表给定二进制矩阵中 1 最多的行的索引。

上述代码的时间复杂度为 0(m*n)，其中 m 是行数，n 是矩阵中的列数。

方法 - 2

我们可以进一步优化上述代码。与其在行中进行二分查找，不如先检查该行是否比迄今为止的最大值有更多的 1。如果行包含更多的 1，那么只需计算行中的 1。我们不需要在完整的行中实现二分查找来查找行中的 1。我们在最后一个最大值的索引之前进行搜索。

让我们理解下面的例子。

示例 -

输出

Index of row with maximum 1s is: 2

解释 -

find_first_one() 方法与我们在前一段代码中解释的相同。find_row_with_max_ones() 函数以矩阵为输入，并返回具有最多 1 的行的索引。我们将 max_ones 初始化为矩阵第一行中第一个 1 的索引，并将 max_row_index 初始化为 0，max_count 初始化为 -1。然后它遍历矩阵的其余行并执行以下检查。

1. 它检查 max_ones 是否不等于 -1（表示之前已找到 1），并且对应于 num_cols - max_ones - 1 列的元素是否为 1。这样做是为了确保当前行有可能比前一个最大行有更多的 1。
2. 如果条件满足，它将调用 find_first_one 函数来查找该行剩余部分中第一个 1 的索引。它还检查该行从该索引到末尾的 1 的数量 (num_cols - index) 是否大于当前最大计数。
3. 如果步骤 2 中的条件满足，它会将 max_ones 更新为 num_cols 和 index 之间的差值，表示行中的 1 的数量。它还会将 max_row_index 更新为当前行索引。
4. 如果步骤 1 中的条件不满足，它会通过查找当前行中第一个 1 的索引来重置 max_ones。

最后，函数返回 max_row_index 的值，它代表给定矩阵中 1 最多的行的索引。

上述代码的时间复杂度为 0(mlogn)，辅助空间为 0(logn)。

方法 - 3

让我们来理解另一种方法。

示例 -

输出

Index of row with maximum 1s is: 2

解释 -

函数 find_row_with_max_ones() 以矩阵为参数。它使用 len() 函数确定矩阵的行数和列数。它将 max_row_index 变量初始化为 0，该变量将存储具有最多 1 的行的索引。

它将 index 变量初始化为 num_cols - 1，这代表最后一列的索引。函数使用 for 循环遍历矩阵的每一行。

在循环内部，将 flag 变量设置为 False，表示当前行是否比前一行有更多的 1。

然后它进入一个 while 循环，该循环检查 index 是否大于或等于 0，并且当前行在该 index 处的元素是否为 1。如果条件为真，它将 flag 变量设置为 True，并将 index 减 1 以移动到前一列。

一旦 while 循环结束，它就会检查 flag 是否为 True，表明当前行比前一行有更多的 1。如果 flag 为 True，它会将 max_row_index 更新为当前行索引。

循环结束后，它会检查一种特殊情况，即最大行索引为 0 且第一行的最后一个元素为 0。如果此条件为真，则返回 0。最后，它返回 max_row_index。

时间复杂度：上述代码的时间复杂度为 O(m+n)，其中 m 是矩阵的行数，n 是矩阵的列数。