1337.md

1337. The K Weakest Rows in a Matrix

Leetcode link

解题思路

本题给了我们一个二维数组，要求我们返回前 k 弱的数组下标，对于 “弱” 题目的定义是：

1. 数组中 “1” 的个数越少越弱
2. 如果 “1” 的个数相同，那么下标越小的越弱

明白了题目之后，我们只需要做两件事就可以了：

1. 计算每个数组的 “1” 的个数，然后将他们依据上述规则排序
2. 按照排序结果，输出头 k 个的下标

C++

class Solution {
 public:
  // 排序规则
  struct cmp {
    bool operator()(pair<int, int>& a, pair<int, int>& b) {
      if (a.second == b.second) {
        return a.first > b.first;
      } else {
        return a.second > b.second;
      }
    }
  };

  vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;
    for (int i = 0; i < mat.size(); i++) {
      int sum = 0;
      // 计算数组中 1 的个数（根据题目，只要出现一个 0 后面的都是 0，所以直接略过）
      for (int j = 0; j < mat[i].size(); j++) {
        if (mat[i][j] == 0) break;
        sum += 1;
      }
      pq.push({i, sum});
    }
    vector<int> result;
    // 看题目要几个就给他几个
    for (int i = 0; i < k; i++) {
      result.push_back(pq.top().first);
      pq.pop();
    }
    return result;
  }
};

Javascript

var kWeakestRows = function(mat, k) {
    const arr = [];
    for(let i=0;i<mat.length;i++) {
        arr.push([i, mat[i].reduce((a,b)=>a+b)])
    }
  	// 先按照规则排序，之后取得前 k 个之后把他们的下标组合为一个数组
    return arr.sort((a,b)=>a[1] === b[1] ? a[0] - b[0] : a[1] - b[1]
    ).slice(0,k).map(row=>row[0])
};