1439. Find the Kth Smallest Sum of a Matrix With Sorted Rows

题目信息

题号:

1439

难度:

Hard

主题:

堆、二分查找、组合枚举

原题:

LeetCode 1439

重点:

从矩阵每一行恰好选择一个元素并求和;所有行均按非递减顺序排列,返回所有组合和中的第 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
解释:每个组合只需从唯一一行选择一个元素。