Go语言程序：查找排序矩阵行中 1 的最大数量

---

在编程语言中，我们可以创建二维矩阵并在其中存储元素。二维矩阵是一种具有行和列的数据结构。在本文中，我们将介绍两种不同的逻辑来查找矩阵中排序行中 1 的最大数量。

例如，我们有以下矩阵

{0, 1, 1, 1}，1 的数量 = 3

{0, 0, 1, 1}，1 的数量 = 2

{1, 1, 1, 1}，1 的数量 = 4

{0, 0, 0, 0}，1 的数量 = 0

在第三行，我们有 4 个 1，比其他行都多。

方法 1

在这种方法中，我们将使用嵌套 for 循环，在循环中迭代数组并计算 1 的数量，最后返回最大计数。此方法的时间复杂度为 O(N*M)，其中 N 是行的大小，M 是矩阵列的大小。

算法

步骤 1：导入所需的包。

步骤 2：程序首先从主函数开始。

• 在主函数内部，我们首先声明一个大小为 4X4 的二维矩阵。

• 稍后，我们将调用 max1in2DMatrix() 函数，该函数返回一行中 1 的最大数量。

• 最后，我们打印上一步返回的值。

步骤 3：在 max1in2DMatrix() 函数中

• 我们声明一个 maxCount 变量，其中我们存储 0 作为值。

• 然后我们运行嵌套 for 循环。

• 外部循环用于迭代所有行。

• 在内部循环中，我们计算该行中 1 的数量。

• 最后，我们返回该数字。

示例

这是查找二维矩阵中最大 1 的代码，通过在矩阵上运行嵌套循环，并在每次迭代中查找每行中 1 的数量，并更新保存最大 1 计数的变量。

package main

import "fmt"

// function to find the maximum number of 1 in a row
// having 2D array and int variables as arguments and
// int return type
func max1in2DMatrix(matrix [4][4]int, n int, m int) int {
    // declaring and initializing a variable to store the max count
    var maxCount int
    maxCount = 0

    // running nested for loop to iterate over the matrix and
    // count no. of ones in each row
    for i := 0; i < n; i++ {
        count := 0
        for j := 0; j < m; j++ {
            if matrix[i][j] == 1 {
                count++
            }
        }
        if maxCount < count {
            maxCount = count
        }
    }
    // returning the max count
    return maxCount
}

func main() {
    // creating a 2-dimensional array with 0 and 1 as value
    matrix := [4][4]int{
        {0, 1, 1, 1},
        {0, 0, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0},
    }

    fmt.Println("Golang program to find the maximum number of 1 in a row using a for loop.")

    // calling a function with matrix name and size as parameters
    maxCount := max1in2DMatrix(matrix, 4, 4)

    fmt.Println("The maximum number of 1 in the array is", maxCount)
}

输出

Golang program to find the maximum number of 1 in a row using a for loop.
The maximum number of 1 in the array is 4

方法 2

在这种方法中，我们将使用二分查找算法查找一行中 1 的最大数量。二分查找算法是一种搜索算法，用于在排序数组中查找元素，时间复杂度为 O(logN)。使用二分查找算法，此方法的时间复杂度将为 O(NlogM)，其中 N 是行的大小，M 是列的大小。

算法

步骤 1：导入所需的包

步骤 2：程序首先从主函数开始。

• 在主函数内部，我们首先声明一个大小为 4X4 的二维矩阵。

• 稍后，我们将调用 max1in2DMatrix() 函数，该函数返回一行中 1 的最大数量。

• 最后，我们打印上一步返回的值。

步骤 3：在 max1in2DMatrix() 函数中

• 我们声明一个 maxCount 变量，其中我们存储 0 作为值。

• 接下来，我们对每一行运行 for 循环。

• 在 for 循环内部，我们调用 binarySearch() 函数，在该函数中我们查找第一个 1 出现的位置。

• 最后，我们返回矩阵一行中 maxCount 的值。

示例

这是查找二维矩阵中最大 1 的代码，通过对每一行进行排序并应用二分查找来查找 1 出现的位置，并将该位置从数组的大小中减去，将告诉我们该行中 1 的总数。

package main

import "fmt"

// recursive function to find the pivot point where the first one occurs
// using the binary search and having array and integers as arguments
func binarySearch(array [4]int, l int, r int) int {
    if l <= r {
        // find the midpoint in the current array
        m := l + (r-l)/2
        // condition to see if first one is starting from current index
        if (m == 0 || array[m-1] == 0) && array[m] == 1 {
            return m
        } else if array[m] == 0 {
            return binarySearch(array, m+1, r)
        } else if array[m] == 1 {
            return binarySearch(array, l, m-1)
        }
    }
    return -1
}

// function to find the maximum number of 1 in a row
// having 2D array and int variables as arguments and
// int return type
func max1in2DMatrix(matrix [4][4]int, n int, m int) int {
    // declaring and initializing variable to store max count
    var maxCount int
    maxCount = 0

    // running for loop to iterate over each row of matrix and
    // call binary search function to find the point where 1 is starting
    for i := 0; i < n; i++ {
        // calling the binary search function to find the pivot point
        count := binarySearch(matrix[i], 0, 3)
        if count != -1 && maxCount < 4-count {
            maxCount = 4 - count
        }
    }
    // returning the max count
    return maxCount
}

func main() {
    // creating a 2 dimensional array with 0 and 1 as value
    matrix := [4][4]int{
        {0, 1, 1, 1},
        {0, 0, 1, 1},
        {1, 1, 1, 1},
        {0, 0, 0, 0},
    }

    fmt.Println("Golang program to find the maximum number of 1 in a row using the binary search algorithm.")

    // calling a function with matrix name and size as parameters
    maxCount := max1in2DMatrix(matrix, 4, 4)

    fmt.Println("The maximum number of 1 in the array is", maxCount)
}

输出

Golang program to find the maximum number of 1 in a row using the binary search algorithm.
The maximum number of 1 in the array is 4

结论

这些是查找矩阵一行中最大 1 的两种方法。如果我们比较哪种方法在时间方面更有效，那么当我们使用合适的算法时，时间就会减少，这就是为什么第二种方法更有效，因为我们使用了二分查找算法。要了解有关 Golang 的更多信息，您可以浏览这些教程。