Leetcode-The-K-Weakest-Rows-in-a-Matrix

Leetcode 1337. The K Weakest Rows in a Matrix 解題心得

題目: 1337. The K Weakest Rows in a Matrix

題目描述

在這道題目中，我們被給予一個 m * n 的二維矩陣 mat，其中 mat[i][j] 代表第 i 行士兵在第 j 列的狀態（1 為存在，0 為不存在），且每行的士兵狀態是非遞增的。我們需要找出矩陣中前 k 個最弱的行（即士兵數量最少的行），並回傳他們的索引值。若有多行士兵數量相同，則選擇索引較小的行。

大概像這樣：

Example 1:

Input: 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]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 2 
- Row 1: 4 
- Row 2: 1 
- Row 3: 2 
- Row 4: 5 
The rows ordered from weakest to strongest are [2,0,3,1,4].

解題思路

這題的解法很直覺，就是先計算每一排的人數，然後再排序，最後回傳前 k 個排的索引值。

Code

一行解法：

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        return list(map(lambda x:x[0],sorted({idx:it for idx,it in enumerate(list(map(sum,mat)))}.items(), key=lambda x: x[1])[:k]))

這裡使用了蠻多的 lambda，與 map，以及生成式。
簡單解釋一下：

1. list(map(sum,mat)) 會將 mat 中的每一排加總，並回傳一個 list。
2. enumerate 會回傳一個 tuple，第一個元素是索引值，第二個元素是 list(map(sum,mat)) 中的元素。
3. sorted 會將 enumerate 的結果依照第二個元素排序，並回傳一個 list(tuple)。
4. [:k] 會回傳排序後的前 k 個元素。

大致上是這些，然後生成式跟map使用得當，可以讓程式碼更簡潔。

Runtime 100 ms Beats 86.17%

Memory 16.6 MB Beats 94.18%