【LeetCode】矩阵中战斗力最弱的 K 行 Java 题解
题目描述
给你一个大小为 m * n 的矩阵 mat,矩阵由若干军人和平民组成,分别用 1 和 0 表示。
请你返回矩阵中战斗力最弱的 k 行的索引,按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。
复制代码
思路分析
这是一个简单题目,首先需要理解题意,题意简述为,统计每一个子数组中 1 的个数,根据 1 的个数对二维数组索引进行排序,当 1 的个数相同的时候,按照自然升序排序。
首先使用朴素解法,使用 TreeMap 数据结构,实现了排序功能。
代码
复制代码
总结
上述代码的时间复杂度是 O(n * m), 空间复杂度是 O(n)
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/904fb504178a7755f198dc8dd】。文章转载请联系作者。
评论