2021-08-13：给定一个每一行有序、每一列也有序，整体可

原创

福大大架构师每日一题

修改于 2021-08-16 02:22:08

3450

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

2021-08-13：给定一个每一行有序、每一列也有序，整体可能无序的二维数组，在给定一个正数k，返回二维数组中，最小的第k个数。

福大大答案2021-08-13：

二分法。

代码用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
    }
}