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

蚊子前端博客
发布于 2021-09-14 09:42
这个题目比较简单,不过我这里提供了另一种解题思路,供大家参考!

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

COPYSHELL

给你一个大小为 m * n 的矩阵 mat,矩阵由若干军人和平民组成,分别用 1 和 0 表示。 请你返回矩阵中战斗力最弱的 k 行的索引,按从最弱到最强排序。 如果第 i 行的军人数量少于第 j 行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。 军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。

这里有个矩阵:

COPYJAVASCRIPT

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 语言来实现一下:

COPYCPP

// 升序 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 开始计数),对权重再进行取余后,得到的一定是行号。

棒棒哒-蚊子的前端博客

听懂掌声!

标签:
阅读(1165)

公众号:

qrcode

微信公众号:前端小茶馆