栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

leetcode1337. 矩阵中战斗力最弱的K行

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

leetcode1337. 矩阵中战斗力最弱的K行

LeetCode系列文章

文章目录
  • 一、题目描述
  • 二、示例
  • 三、主体思路
  • 四、代码实现

一、题目描述

  给你一个大小为 m × n mtimes 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的个数,构成<1的个数,行号>的键值对。
  2. 用各行的战斗力进行建堆(小堆)。
  3. 从堆顶取出战斗力最弱的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)。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/983903.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号