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 的更多資訊，您可以瀏覽這些教程。