给定一个每一行有序、每一列也有序，整体可能无序的二维数组 ，在给定一个正数k，返回二维数组中，最小的第k个数。
二分法。
代码用golang编写。代码如下：
package main
import (
"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
}
}执行结果如下：
