给你一个大小为 m * n
的矩阵 mat
,矩阵由若干军人和平民组成,分别用 1 和 0 表示。
请你返回矩阵中战斗力最弱的 k
行的索引,按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行,或者两行军人数量相同但 i 小于 j,那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置,也就是说 1 总是出现在 0 之前。
示例 1:
输入: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]
示例 2:
输入:mat = [[1,0,0,0], [1,1,1,1], [1,0,0,0], [1,0,0,0]], k = 2 输出:[0,2] 解释: 每行中的军人数目: 行 0 -> 1 行 1 -> 4 行 2 -> 1 行 3 -> 1 从最弱到最强对这些行排序后得到 [0,2,3,1]
提示:
m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j]
不是 0 就是 1
二分查找 + 排序。
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
m, n = len(mat), len(mat[0])
ans = [n - bisect_right(row[::-1], 0) for row in mat]
idx = list(range(m))
idx.sort(key=lambda i: ans[i])
return idx[:k]
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
int m = mat.length, n = mat[0].length;
int[] res = new int[m];
List<Integer> idx = new ArrayList<>();
for (int i = 0; i < m; ++i) {
idx.add(i);
int[] row = mat[i];
int left = 0, right = n;
while (left < right) {
int mid = (left + right) >> 1;
if (row[mid] == 0) {
right = mid;
} else {
left = mid + 1;
}
}
res[i] = left;
}
idx.sort(Comparator.comparingInt(a -> res[a]));
int[] ans = new int[k];
for (int i = 0; i < k; ++i) {
ans[i] = idx.get(i);
}
return ans;
}
}
function kWeakestRows(mat: number[][], k: number): number[] {
let n = mat.length;
let sumMap = mat.map((d, i) => [d.reduce((a, c) => a + c, 0), i]);
let ans = [];
// 冒泡排序
for (let i = 0; i < k; i++) {
for (let j = i; j < n; j++) {
if (
sumMap[j][0] < sumMap[i][0] ||
(sumMap[j][0] == sumMap[i][0] && sumMap[i][1] > sumMap[j][1])
) {
[sumMap[i], sumMap[j]] = [sumMap[j], sumMap[i]];
}
}
ans.push(sumMap[i][1]);
}
return ans;
}
class Solution {
public:
int search(vector<int>& m) {
int l = 0;
int h = m.size() - 1;
while (l <= h) {
int mid = l + (h - l) / 2;
if (m[mid] == 0)
h = mid - 1;
else
l = mid + 1;
}
return l;
}
vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
vector<pair<int, int>> p;
vector<int> res;
for (int i = 0; i < mat.size(); i++) {
int count = search(mat[i]);
p.push_back({count, i});
}
sort(p.begin(), p.end());
for (int i = 0; i < k; i++) {
res.push_back(p[i].second);
}
return res;
}
};
func kWeakestRows(mat [][]int, k int) []int {
m, n := len(mat), len(mat[0])
res := make([]int, m)
var idx []int
for i, row := range mat {
idx = append(idx, i)
left, right := 0, n
for left < right {
mid := (left + right) >> 1
if row[mid] == 0 {
right = mid
} else {
left = mid + 1
}
}
res[i] = left
}
sort.Slice(idx, func(i, j int) bool {
return res[idx[i]] < res[idx[j]] || (res[idx[i]] == res[idx[j]] && idx[i] < idx[j])
})
return idx[:k]
}