发布时间:2024-06-07 17:01
LeetCode系列文章
给你一个大小为 m × n m\times n m×n的矩阵 m a t mat mat,矩阵由若干军人和平民组成,分别用 1 1 1 和 0 0 0 表示。
请你返回矩阵中战斗力最弱的 k k k 行的索引,按从最弱到最强排序。
如果第 i i i 行的军人数量少于第 j j j 行,或者两行军人数量相同但 i i i 小于 j j j,那么我们认为第 i i i 行的战斗力比第 j j j 行弱。
军人总是排在一行中的靠前位置,也就是说 1 1 1 总是出现在 0 0 0 之前。
输入: mat = [ [1, 1, 0, 0, 0 ],
[1, 1, 1, 1, 0 ],
[1, 0, 0, 0, 0 ],
[1, 1, 1, 1, 1 ] ],
k = 3
输出: [2, 0, 3]
解释:
每行中的军人数目:
行0 -> 2
行1 -> 4
行2 -> 1
行3 -> 2
行4 -> 5
从最弱到最强对这些行排序后得到 [2, 0, 3, 1, 4]
想要找出矩阵中战斗力最弱的K行,我们可以先将矩阵中的每行按战斗力的强弱进行排序,然后就可以选取出战斗力最弱的K行。
在排序的过程中需要将各行的战斗力进行比较,因此我们需要设置一个战斗力的比较方式。
- 根据题意可知,在比较战斗力时,需要先比较两行中1的个数。
- 若两行中1的个数不同,则1的个数较少的一行战斗力较弱。
- 若两行中1的个数相同,则还需要继续比较行号,行号较小的一行战斗力较弱。
按照该比较方式将各行按战斗力进行排序后,就能够选取出战斗力最弱的K行。
在实现代码时,可以用pair来表示某行的战斗力。
- 将该行中1的个数作为pair当中first成员。
- 将该行的行号作为pair当中的second成员。
因为pair类型变量在比较时默认就是先比较first成员,如果first成员相同再比较second成员,这正好符号该题战斗力的比较规则,而排序的方式可以是任意的,这里以堆排序为例。
因此解题步骤如下:
- 遍历矩阵的各行,统计出每行中1的个数,构成
<1的个数,行号>
的键值对。- 用各行的战斗力进行建堆(小堆)。
- 从堆顶取出战斗力最弱的k行。
- 因为每行中的1总是出现在0之前的,所以在统计某行中1的个数时可以采用二分查找的方式,找到该行中最后那个1的位置pos,此时pos+1对应的就是该行中1的个数。
- 在建堆时,最好不要将每行的pair一个个放入堆中,而应该直接用这若干个pair进行建堆,因为前者的时间复杂度是 O ( N l o g N ) O(NlogN) O(NlogN),而后者的时间复杂度是 O ( N ) O(N) O(N)。