1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows¶
题目信息¶
- 题号:
1439
- 难度:
Hard
- 主题:
堆、二分查找、组合枚举
- 原题:
- 重点:
从矩阵每一行恰好选择一个元素并求和;所有行均按非递减顺序排列,返回所有组合和中的第
k小值
题目重述¶
给定 m x n 整数矩阵 mat,每一行都按非递减顺序排列。从每一行恰好选择一个元素,并把选中元素相加,得到一个组合和。
把全部 n^m 个组合和按非递减顺序排列,请返回第 k 小的值;相同和值由不同选择产生时需要重复计数。
1 <= m, n <= 40,1 <= mat[i][j] <= 5000,1 <= k <= min(200, n^m)。
自建示例¶
相同和值可以由不同组合重复产生:
输入:mat = [[1,3],[2,4]], k = 3
输出:5
解释:四个组合和为 3、5、5、7,第三小值为 5。
只有一行时退化为该行第 k 个元素:
输入:mat = [[1,2,4]], k = 2
输出:2
解释:每个组合只需从唯一一行选择一个元素。