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)``。 自建示例 -------- 相同和值可以由不同组合重复产生: .. code-block:: text 输入:mat = [[1,3],[2,4]], k = 3 输出:5 解释:四个组合和为 3、5、5、7,第三小值为 5。 只有一行时退化为该行第 ``k`` 个元素: .. code-block:: text 输入:mat = [[1,2,4]], k = 2 输出:2 解释:每个组合只需从唯一一行选择一个元素。