###### tags: `Leetcode` `easy` `heap` `python` `c++`

# 1337. The K Weakest Rows in a Matrix

## [題目連結:] https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/description/

## 題目:
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].

## 解題想法:
* 此題為，矩陣中:1表示士兵，0表示村名
* 返回矩陣中，1個數最少的'列'
* 若A列1的個數<B列1個術
* A叫弱
* 若A、B兩列1個數一樣
* 列數叫前者為弱
* 使用heap紀錄:
* 存pair(num of 1, row position)
* 注意
* python中heapq為 **min_heap**
* c++中priority_queue為 **max_heap**

## Python:

from heapq import heappush, heappop
class Solution(object):
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """
        res=[]
        que=[] #存pair (num of 1, row position)
        for row in range(len(mat)):
            num=0
            for val in mat[row]:
                if val==1:
                    num+=1
                else:
                    break
            heappush(que,(num,row))
        for _ in range(k):
            res.append(heappop(que)[1])
        return res

## C++:
* priority_queue< pair<int, int>> que;
* 為max_heap資料預設由大到小排序，即優先權高的資料會先被取出: que.top();
* 加負號讓其變min_heap

class Solution {
public:
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        priority_queue< pair<int, int>> que;
        vector<int> res;
        int num=0;
        for (int row=0; row<mat.size(); row++){
            num=0;
            for (int val: mat[row]){
                if (val==1)
                    num+=1;
                else
                    break;
            }
            pair<int,int> tmp(-num, -row);
            que.push(tmp);
        }
        for (int i=0; i<k; i++){
            res.push_back(-que.top().second);
            que.pop();
        }
        return res;
    }
};