题目名称

给你一个 m * n 的矩阵 mat，以及一个整数 k ，矩阵中的每一行都以非递减的顺序排列。

你可以从每一行中选出 1 个元素形成一个数组。返回所有可能数组中的第 k 个 最小 数组和。

示例

输入：words = [“adc”,”wzy”,”abc”]
输入：mat = [[1,3,11],[2,4,6]], k = 5
输出：7
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,2], [1,4], [3,2], [3,4], [1,6]。其中第 5 个的和是 7

输入：mat = [[1,10,10],[1,4,5],[2,3,6]], k = 7
输出：9
解释：从每一行中选出一个元素，前 k 个和最小的数组分别是：
[1,1,2], [1,1,3], [1,4,2], [1,4,3], [1,1,6], [1,5,2], [1,5,3]。其中第 7 个的和是 9 。

题解

根据题目描述，我们需要找出前 m 行的所有可能数组中的第 k 个最小数组和。

如果我们能够找出前 m−1 行的所有可能数组中的前 k 个最小数组和，那么我们可以将第 m 行的每个元素与前 m−1 行的前 k 个最小数组和相加，将得到的所有结果排序后，取前 k 个最小值，即为前 m 行的所有可能数组中的前 k 个最小值。

因此，我们可以定义一个数组 pre，用于存储此前遍历到的行的前 kkk 个最小数组和，初始时 preprepre 只有一个元素 0。

然后，我们遍历 matmatmat 的每一行 cur，将 cur 中的每个元素与 pre 中的每个元素相加，将得到的所有结果排序后，取前 k 个最小值作为新的 pre。继续遍历下一行，直到遍历完所有行。

最后返回 pre 中的第 k 个数（下标 k−1）即可。
时间复杂度 O(m×n×k×log⁡(n×k))，空间复杂度 O(n×k)。其中 m 和 n 分别是矩阵的行数和列数。

以上是我能看懂的一个题解，换个更简单的意思就是

首先定义一个只有一个数据0的数组，作为存储计算和的容器 sumArr
接下来遍历传入的 mxn 数组，将每行数据分别与 sumArr 中的元素进行加操作，然后取最后和的前K 小的数（因为题目要求只需要第K位最小和，所以只截取前K位可以减少运算步骤）

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(mat, k) {
  let sumArr = [0]
  for(let row = 0; row < mat.length; row++) {
    let next = []
    for(let sumIndex = 0; sumIndex < sumArr.length; sumIndex++) {
      for(let col = 0; col < mat[0].length; col++) {
        next.push(sumArr[sumIndex] + mat[row][col])
      }
    }
    // 为了避免数组过长，毕竟我们只需要最小的数据
    sumArr = next.sort((a, b) => a - b).slice(0, k)
  }
  return sumArr[k-1]
};