排序應用題 The K Weakest Rows in a Matrix Leetcode #1337

題目會給定我們一個二維矩陣，矩陣裡面的1代表一位士兵，

題目定義戰鬥力比較的規則:

士兵少的row戰鬥力比較小。

若有兩條row的戰鬥力相等，

則row index比較小的那條row，戰鬥力比較小。

請選出，前k個戰鬥力最弱的row

測試範例:

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].

Example 2:

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers in each row is: 
- Row 0: 1 
- Row 1: 4 
- Row 2: 1 
- Row 3: 1 
The rows ordered from weakest to strongest are [0,2,3,1].

約束條件:

Constraints:

• The number of nodes in the tree is in the range [1, 100].
• -100 <= Node.val <= 100

演算法:

先掃描過每一個row，統計每個row的戰鬥力，用tuple的形式記錄兩個資訊，
(戰鬥力, row index)。

最後用(戰鬥力, row index)排序好，選出前k個戰鬥力最弱的row，

輸出row index即為所求。

程式碼:

class Solution:
　def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
　　
　　# get the height of matrix
　　h = len(mat)
　　
　　# compute the strength for each row
　　strength = [ (sum(mat[row_idx]), row_idx ) for row_idx in range(h) ]
　　 
　　# sort by 1's count and row index in ascending order
　　strength.sort( key = lambda pair: (pair[0], pair[1]))
　　
　　# pick first k weakest rows
　　return [ strength[i][1] for i in range(k) ]

時間複雜度:

max{ O( hw ) , O( h log h) }

掃描矩陣耗費O(hw)，排序每條row的戰鬥力pair耗費O(h log h)

空間複雜度:

O(h) 額外使用了strength table來儲存戰鬥力。

Reference:

[1] The K Weakest Rows in a Matrix — LeetCode