leetcode1337 矩阵中战斗力最弱的 K 行的一种新颖解法

这是一道难度为“简单”的题目，我们先来看下题干https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix：

给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。

请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。

如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。

军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。

这里有个矩阵：

const mat = [
  [1, 1, 0, 0, 0],
  [1, 1, 1, 1, 0],
  [1, 0, 0, 0, 0],
  [1, 1, 0, 0, 0],
  [1, 1, 1, 1, 1],
];

因为军人总是在最前面，很多人最直观的算法就是，按照列，从上往下找，碰到第一个 0 的那一行就是最小的，遍历个遍，就能把找出最弱的前 K 行了。

1. 一个新颖的思路

但这里我提供了另一种思路：

通过一个公式，计算出每行的战斗值：

该行的军人数量 * 100 + 行号。

按照这个公式，我们来实现一个算法：

1. 每行：该行的军人数量 * 100 + 行号，得到该行的战斗值；

2. 然后按照算出的战斗值进行从小到达的排序；

3. 取前 k 个数据，然后进行取余，即得到结果；

我们用 C 语言来实现一下：

// 升序
int cmp(const void *a, const void *b)
{
    return *(int *) a - *(int *) b;
}

int *kWeakestRows(int **mat, int matSize, int *matColSize, int k, int *returnSize)
{
    static int result[110];
    int i, j, num, weighting;

    weighting = 100;
    for (i = 0; i < matSize; i++)
    {
        num = 0;
        for (j = 0; j < *matColSize; j++)
        {
            if (mat[i][j] == 0)
            {
                break;
            }
            num += mat[i][j];
        }
        result[i] = num * weighting + i; // 军人数量 * 100 + 行号
    }
    qsort(result, matSize, sizeof(result[0]), cmp); // 排序
    *returnSize = k;
    for (i = 0; i < k; i++)
    {
        result[i] = result[i] % weighting; // 取余
    }
    return result;
}

这思路是不是很新颖？可是为什么这么计算，也是正确的呢？

2. 思路的剖析

这里我们要注意题目中给出的两个判断条件：

1. 优先判断军人数量，军人数量少的则战斗力弱；

2. 军人数量相同的，则行号小的战斗力弱；

而最后又需要的是最弱的行号。

因此，我们把军人数量按照一定的权重进行放大后，其实大小关系是没有的，该相等的还是相等，该小的还是小。最后再加上行号，则可以把军人数量和行号两个维度结合算出一个战斗值来。

这个算出来的战斗值就会满足上面的两个判断条件。

2.1 权重值的选择

为什么权重是 100 呢？我们先说下为什么不能小于 100 。假如我们设定权重是 90，上面的算法就会存在一个漏洞：行号的加持超过军人数量。

举个例子，比如第 0 行有 1 个军人，第 99 行有 0 个军人；按照上面的算法，得到第 0 行的战斗值是 90（军人数量 1 * 90 + 行号 0），第 99 行的战斗值是 99（军人数量 0 * 99 + 行号 99），则第 0 行小于第 99 行；但实际上，是第 0 行的战斗力更强（因为军人数量更多）。

题目要求整个战斗矩阵最大只有 100 行，当我们把权重设置成 100 时，则行号再大，也追不上军人数量的加持。

实际上，权重 weighting >= 100 都是没问题的，只不过我们这里取了一个最小的临界值而已。

2.2 最后的那一步取余

取余这个操作，就是为了得到我们的行号。我们选择加持的权重的值大于最大行的行号（从 0 开始计数），对权重再进行取余后，得到的一定是行号。

听懂掌声！