Golang 在矩阵的排序行中找到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： 首先程序将从main函数开始。

• 在main函数中，首先声明大小为4X4的二维矩阵。

• 接着我们调用max1in2DMatrix()函数，该函数返回矩阵中一行中最多的1的个数。

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

  步骤3： 在max1in2DMatrix()函数中

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

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

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

• 在内部循环中，我们计算该行中的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作为初始值存储其中。

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

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

• 最后，我们返回矩阵中一行中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的信息，您可以查看这些教程。