矩陣中戰斗力最弱的 K 行
一、題目
給你一個大小為 m * n 的矩陣 mat，矩陣由若干軍人和平民組成，分別用 1 和 0 表示，
請你回傳矩陣中戰斗力最弱的 k 行的索引，按從最弱到最強排序，
如果第 i 行的軍人數量少于第 j 行，或者兩行軍人數量相同但 i 小于 j，那么我們認為第 i 行的戰斗力比第 j 行弱，
軍人 總是 排在一行中的靠前位置，也就是說 1 總是出現在 0 之前，
示例：
輸入：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
輸出：[2,0,3]
解釋：
每行中的軍人數目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
從最弱到最強對這些行排序后得到 [2,0,3,1,4]
二、題解
- 單獨分析每一行，并記錄原始下標和目標個數
- 篩選符合題目的資料并回傳
/**
* @param {number[][]} mat
* @param {number} k
* @return {number[]}
*/
var kWeakestRows = function(mat, k) {
const len = mat.length;
const arr = [];
for (let i = 0; i < len; i++) {
arr.push({ index: i, count: countS(mat[i]) });
}
arr.sort((a, b) => {
if (a.count === b.count) return a.index - b.index;
return a.count - b.count;
});
return arr.slice(0, k).map(({ index }) => index);
};
// 只有統一單行的時候使用了2分法
const countS = function(nums) {
const len = nums.length;
let left = 0;
let right = len - 1;
if (nums[right] === 1) return len;
while (left <= right) {
const mid = left + ((right - left) >> 1);
if (nums[mid] === 1) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
};
三、寫在最后
本文是附加題，可能僅僅借助了二分思想中的一部分，加油！
如果對你有所幫助不妨給本專案的github 點個 star，這是對我最大的鼓勵
關于我
- 花名：余光
- WX：j565017805
- 沉迷 JS，水平有限，虛心學習中
其他沉淀
- 前端進階筆記
- JS 版 LeetCode 題解
- CSDN
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/238552.html
標籤：其他
上一篇：使用無線串口進行單片機通信
下一篇：高級數理邏輯試卷參考答案