前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >2021-08-13:给定一个每一行有序、每一列也有序,整体可能无序的二维数组 ,在给定一个正数k,返回二维数组中,最小的第k个

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

作者头像
福大大架构师每日一题
发布2021-09-03 15:22:47
1.3K0
发布2021-09-03 15:22:47
举报

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

福大大 答案2021-08-13:

二分法。

代码用golang编写。代码如下:

代码语言:javascript
复制
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
    }
}

执行结果如下:

***

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

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2021-08-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 福大大架构师每日一题 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档