LeetCode 1337 - 矩阵中战斗力最弱的 K 行

Algorithm LeetCode
August 1, 2021
简单
原题链接：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 之前。

Python题解

个人题解

class Solution(object):
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """
        powers = []
        for i in range(len(mat)):
            power = 0
            for column in mat[i]:
                power += column
                if column == 0:
                    break
            powers.append((power, i))
        powers.sort()
        ans = []
        for power, row in powers:
            if len(ans) == k:
                break
            ans.append(row)
        return anspython

总结

题比较简单，但是官方题解有两个比较高级的解法。
一个是二分查找+堆，另一个是二分查找+快速选择。（看不懂）
The End