LeetCode: 1337-The K Weakest Rows in a Matrix 解題紀錄

Last Updated on 2022-03-27 by Clay

題目

You are given an m x n binary matrix mat of 1‘s (representing soldiers) and 0‘s (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1‘s will appear to the left of all the 0‘s in each row.

A row i is weaker than a row j if one of the following is true:

• The number of soldiers in row i is less than the number of soldiers in row j.
• Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

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:

• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100
• 1 <= k <= m
• matrix[i][j] is either 0 or 1.

輸入一個列表，列表中存在著 1 跟 0 等數值，其中 1 出現的次數越多代表越強、而當 1 出現的次數相同時，越早出現的列表越弱（假設第一行跟第三行的 1 數量皆為二，那第一行比第三行更弱）。

我們還對得到一個 k 值，代表著我們要返回的最弱行號數量。

簡單來講就是從弱到強排序，並返回前 k 個行號。

---

解題思路

排序法

這題我的第一感就是使用排序法來解。排序的單位是一組陣列，第一個元素代表著『1 的數量』、第二個元素代表著『行號』。

而預設的 sort() 函式，在我所用於解題的 C++ 和 Python 語言當中，都是先按照第一個元素排序、若第一個元素相同則按照第二個元素排序 —— 剛好完美符合我的需求。

最後，則返回前 k 個元素的行號即可。

排序法複雜度

由於需要經過排序，故時間複雜度為 n log(n)。然後由於要儲存跟輸入列表同等長度的『 1 的數量』跟『行號』，空間複雜度自然也是 O(n)。

Time complexity	O(n log n)
Space complexity	O(n)

排序法 C++ 範例程式碼

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        // Init
        vector<pair<int, int>> v;
        
        // Count
        for (int i=0; i<mat.size(); ++i) {
            int temp = std::accumulate(mat[i].begin(), mat[i].end(), 0);
            v.push_back(pair{temp, i});
        }
        
        // Sort
        sort(v.begin(), v.end());
        
        // Pop
        while (v.size() > k) {
            v.pop_back();
        }
        
        // Return
        vector<int> results;
        for (int i=0; i<v.size(); ++i) {
            results.push_back(v[i].second);
        }
        
        return results;
    }
};

排序法 Python 範例程式碼

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        # Init
        v = [] 
        
        # Count
        for i in range(len(mat)):
            v.append([sum(mat[i]), i])
        
        # Sort
        v.sort()
        
        # Pop
        v = v[:k]
        
        # Return
        v = [item[1] for item in v]
        
        return v;

---

References

• https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

---

Read More

• LeetCode 解題紀錄目錄