矩阵中战斗力最弱的 K 行 图解题解
这道题到底在问什么
- 输入
- mat=[[1,0],[1,1]], k=1
- 输出
- [0]
- 输入
- mat=[[1,1,0],[1,0,0],[1,1,1]], k=2
- 输出
- [1,0]
先想最直接的笨办法
现在每行军人数都有了。排序规则有两条:军人数少的更弱,排在前面;军人数一样时,行号小的更弱。咱们就照这个规则,从最弱的一行开始,一个一个往答案里挑。（动画第 19 步）
最优解：一步一步想明白
- 3记牢这三步:数军人、按军人数和行号排序、取前 k 行。下面每一帧都在套这三步,先从数军人开始。
- 4绿格 = 军人(1),蓝格 = 平民(0)这就是 4 行 5 列的矩阵,绿色格子是军人也就是 1,蓝色格子是平民也就是 0。每行 1 都挤在左边。右边面板要记下每行的军人数,现在还空着。咱们一行一行来,从行 0 开始,从左往右数 1。
- 5橙格 = 正在看的格子看行 0 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
- 6橙格 = 正在看的格子看行 0 的第 1 格,是 1,一名军人,军人数加到 2。这一格是军人,继续往右看下一格。
- 7橙格 = 停下的第一个平民行 0 的第 2 格是 0,平民,数 1 到此为止。这行一共 2 名军人,记进右边面板。
- 8橙格 = 正在看的格子看行 1 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
- 9橙格 = 正在看的格子看行 1 的第 1 格,是 1,一名军人,军人数加到 2。这一格是军人,继续往右看下一格。
- 10橙格 = 正在看的格子看行 1 的第 2 格,是 1,一名军人,军人数加到 3。这一格是军人,继续往右看下一格。
- 11橙格 = 正在看的格子看行 1 的第 3 格,是 1,一名军人,军人数加到 4。这一格是军人,继续往右看下一格。
- 12橙格 = 停下的第一个平民行 1 的第 4 格是 0,平民,数 1 到此为止。这行一共 4 名军人,记进右边面板。
- 13橙格 = 正在看的格子看行 2 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
- 14橙格 = 停下的第一个平民行 2 的第 1 格是 0,平民,数 1 到此为止。这行一共 1 名军人,记进右边面板。
- 15橙格 = 正在看的格子看行 3 的第 0 格,是 1,一名军人,军人数加到 1。这一格是军人,继续往右看下一格。
- 16橙格 = 正在看的格子看行 3 的第 1 格,是 1,一名军人,军人数加到 2。这一格是军人,继续往右看下一格。
- 17橙格 = 停下的第一个平民行 3 的第 2 格是 0,平民,数 1 到此为止。这行一共 2 名军人,记进右边面板。
- 18军人数 = 2、4、1、2四行都数完了。行 0 有 2 名,行 1 有 4 名,行 2 只有 1 名,行 3 有 2 名。军人数就是 2、4、1、2。注意行 0 和行 3 都是 2 名,打平了,这种平局等会儿要靠行号来分高下。下面进入排序。
- 19军人数少的更弱;平局看行号现在每行军人数都有了。排序规则有两条:军人数少的更弱,排在前面;军人数一样时,行号小的更弱。咱们就照这个规则,从最弱的一行开始,一个一个往答案里挑。
- 20橙格 = 已入答案的行先找军人数最少的。行 2 只有 1 名军人,是全场最少,妥妥的最弱一行。把行 2 第一个放进答案,现在答案是 [2]。
- 21浅橙 = 正在比较的两行接着找次弱的。剩下行 0、行 1、行 3,军人数分别是 2、4、2。最少的是 2,但行 0 和行 3 都是 2 名,打平了。这时候看行号:行 0 的行号比行 3 小,所以行 0 更弱,该它先走。
- 22橙格 = 已入答案的行平局靠行号小的更弱,行 0 胜出,排在行 3 前面。把行 0 放进答案,现在答案是 [2, 0]。还差一行就凑齐 3 个了。
- 23橙格 = 已入答案的行剩下行 1 和行 3,军人数 4 和 2。行 3 的 2 名更少,更弱,该它了。把行 3 放进答案,现在答案是 [2, 0, 3],正好凑满 3 行。剩下行 1 有 4 名军人,是最强的,排最后,用不上。
- 24弱 → 强:行2、行0、行3、行1把四行从弱到强排满就是行 2、行 0、行 3、行 1,对应军人数 1、2、2、4。其中行 0 和行 3 这对平局,靠行号让行 0 在前。k 是 3,只取最前面三行,后面的行 1 灰掉不要。
- 25战斗力最弱的 3 行战斗力最弱的 3 行,从弱到强就是行 2、行 0、行 3,答案数组是 [2, 0, 3]。这就是整道题:数清每行军人,按军人数和行号排序,取最弱的前 k 行行号。
⚠️ 容易写错的地方
✗ 错：把「战斗力」想成别的指标
✓ 对：战斗力就看军人数,也就是这行 1 的个数
1 越多越强、越少越弱,数清前导 1 的个数是整道题的根
✗ 错：军人数相同时忘了比行号或比反了
✓ 对：军人数一样时,行号小的更弱、排在前面
行 0 和行 3 都是 2 名,行号 0 比 3 小,所以行 0 更弱在前,搞反顺序答案就错
✗ 错：只按军人数排却用了不稳定排序
✓ 对：要么把(军人数,行号)一起当关键字排,要么用稳定排序
不稳定排序会打乱平局两行的原始行号次序,导致平局顺序错乱
✗ 错：返回成军人数或忘了只取前 k
✓ 对：返回的是行的索引,而且只取最弱的前 k 个
题目要的是行号列表、长度是 k,不是每行的军人数
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
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;
}
};Java
import java.util.*;
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;
}
}复杂度
时间
C++/Java O(m·log n + m·log m);Python O(m·n + m·log m)
m 是行数,n 是列数。数每行军人:C++/Java 用二分是 O(log n),m 行共 O(m·log n);Python 用逆序切片反转每行再 bisect,反转就是 O(n),m 行共 O(m·n)(和直接从左扫同阶,慢在反转那一抄)。给 m 行按(军人数,行号)排序三家都是 O(m·log m)。整体由这两部分相加,差别只在数军人那块
空间
O(m)(Python 反转额外 O(n))
存每行军人数和行号这一组数据是 O(m),答案数组 O(k)。Python 每行逆序切片会另抄一份长度 n 的临时行,峰值多占 O(n)。排序内部开销:C++ 与 Java 约 O(log m) 递归栈,Python 的 sort 最坏 O(m),按峰值整体记 O(m)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 矩阵中战斗力最弱的 K 行 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
数每行军人,为什么能用二分,比从左扫快在哪?+
因为题目保证每行 1 都排在 0 前面,这一行其实是有序的,前半段全 1、后半段全 0。要找 1 和 0 的分界点,就是在有序数组里找第一个 0 的位置,二分一下就能定位,时间是 O(log n);从左一个个扫是 O(n)。当每行很长时,二分明显更快。
平局时为什么稳定排序能自动按行号升序,不用显式比行号?+
一开始行号本来就是 0、1、2 这样从小到大排列的。稳定排序的特点是,关键字相等时保持元素的原始先后。所以只按军人数排,军人数相同的几行会保持它们原来的行号升序,正好满足「行号小的更弱在前」。C++ 里更直接,把(军人数,行号)打包成一对排序,平局自动按行号,一眼就看明白。
如果 k 远小于行数,有没有更省的办法?+
可以用一个大小为 k 的大顶堆,按(军人数,行号)从强到弱比较。遍历每行,把(军人数,行号)入堆,堆超过 k 个就弹掉当前最强的那个。扫完后堆里剩下的就是最弱的 k 行,再按弱到强整理输出。堆维护部分是 O(m·log k);但每行入堆前还要数军人,所以总时间:C++/Java 为 O(m·log n + m·log k),Python 当前反转写法为 O(m·n + m·log k)。当 k 远小于行数 m 时,堆维护那部分比整体排序更省。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 矩阵中战斗力最弱的 K 行 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。