2021-08-13：給定一個每一行有序、每一列也有序，整體可能無序的二維陣列 ，在給定一個正數k，返回二維陣列中，最小的第k個數。

福大大 答案2021-08-13：

二分法。

程式碼用golang編寫。程式碼如下：

package mainimport (    "fmt"    "math")func main() {    matrix := [][]int{{1, 2, 3}, {2, 3, 4}, {3, 4, 5}}    ret := kthSmallest2(matrix, 8)    fmt.Println(ret)}// 二分的方法func kthSmallest2(matrix [][]int, k int) int {    N := len(matrix)    M := len(matrix[0])    left := matrix[0][0]    right := matrix[N-1][M-1]    ans := 0    for left <= right {        mid := left + ((right - left) >> 1)        // <=mid 有幾個 <= mid 在矩陣中真實出現的數，誰最接近mid        info := noMoreNum(matrix, mid)        if info.num < k {            left = mid + 1        } else {            ans = info.near            right = mid - 1        }    }    return ans}type Info struct {    near int    num  int}func NewInfo(n1 int, n2 int) *Info {    ans := &Info{}    ans.near = n1    ans.num = n2    return ans}func noMoreNum(matrix [][]int, value int) *Info {    near := math.MinInt64    num := 0    N := len(matrix)    M := len(matrix[0])    row := 0    col := M - 1    for row < N && col >= 0 {        if matrix[row][col] <= value {            near = getMax(near, matrix[row][col])            num += col + 1            row++        } else {            col--        }    }    return NewInfo(near, num)}func getMax(a int, b int) int {    if a > b {        return a    } else {        return b    }}

執行結果如下：

***

[左神java程式碼](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class17/Code02_KthSmallestElementInSortedMatrix.java)