LeetCode刷题-矩阵中战斗力最弱的K行
前言说明
算法学习，日常刷题记录。
题目连接
题目内容
给你一个大小为m * n的矩阵mat，矩阵由若干军人和平民组成，分别用1和0表示。
请你返回矩阵中战斗力最弱的k行的索引，按从最弱到最强排序。
如果第i行的军人数量少于第j行，或者两行军人数量相同但i小于j，那么我们认为第i行的战斗力比第j行弱。
军人总是排在一行中的靠前位置，也就是说1总是出现在0之前。
示例1:
输入：mat =
k = 3
输出：[2,0,3]
解释：
每行中的军人数目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
示例2:
输入：mat =
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
分析过程
这里一共3种方法，从方法1到方法3，逐步优化。
方法2，在方法1的基础上进行优化。
方法3，在方法2的基础上再进行优化。
方法1
思路：统计每行的军人数目，使用改造后的冒泡排序进行排序，取排序后的前k个。
注意：这里的排序是按照每行军人数目来进行排序的，但是需要取出的结果却是对应的行标，而不是每行的军人数目，所以这里列表来保存每行的军人数目，列表的元素使用一个数组，数组再用两个元素分别保存每行的军人数目和行标。
第一步
定义列表list，用数组int[]保存每个元素，数组int[]的第1个元素保存行标，第2个元素保存这行的军人数目。
第二步
遍历矩阵mat的行：
1、获取矩阵mat的行row。
2、定义军人数目count，初始为0。
3、遍历每行row的列，具体如下：
若元素是1，那么就是军人，军人数目count加1。
4、保存每行的军人数目count到列表list，用数组表示，数组的第1个元素保存行标i，第2个元素保存这行的军人数目count。
第三步
改造冒泡排序，平时冒泡排序用来对数组int[]进行排序，但这里用来对列表list进行排序，并且列表元素是数组，如下：
1、同样需要进行排序的趟数刚好为列表list的长度减1，每一趟排序找出当前的最大数，挪到对应的位置，这里进行第一层for循环。
2、在第一层for循环时，添加标识isFlag，判断列表list是否已经有序，初始为true，然后进行第二层for循环。
3、在第二层for循环时，每一趟排序时，不断比较当前元素和下一个元素谁大，把大的元素往后挪。
因为列表list的元素是数组int[]，数组的第2个元素保存的是军人数目，所以这里进行比较的元素是数组的第2个元素。
若当前军人数目大于下一军人数目，交换两者对应的列表list的元素。
因为出现交换，所以列表list还不是有序，把标识isFlag设为false。
4、结束第二层for循环时，若标识isFlag是true，那么列表list已经有序，结束第一层for循环，否则第一层for循环继续，直到结束。
第四步
定义结果数组nums，用来保存排序后的前k行军人数目。
从0循环到k-1，构造结果数组nums，循环时：
直接把排序后的列表list的行标赋值给结果数组nums。
第五步
返回结果数组nums。
解答代码
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
// 思路：统计每行的军人数目，使用改造后的冒泡排序进行排序，取排序后的前k个
// 定义列表list，用数组int[]保存每个元素，数组int[]第一个元素保存行标，第二个元素保存这行的军人数目
List<int[]> list = new ArrayList<>();
// 遍历矩阵mat的行
for (int i = 0; i < mat.length; ++i) {
// 获取矩阵mat的行
int[] row = mat[i];
// 定义军人数目，初始为0
int count = 0;
// 遍历每行的列
for (int col : row) {
if (1 == col) {
// 若元素是1，那么就是军人，军人数目加1
++count;
}
}
// 保存每行的军人数目到列表list，用数组表示，数组的第一个元素保存行标，第二个元素保存这行的军人数目
list.add(new int[]{i, count});
}
// 改造冒泡排序，平时冒泡排序用来对数组int[]进行排序，但这里用来对列表list进行排序，并且列表元素是数组，，平均时间复杂度O(n^2)，最好时间复杂度O(n)，最坏时间复杂度O(n^2)，空间复杂度O(1)
// 需要进行排序的趟数刚好为列表list的长度减1，每一趟排序找出当前的最大数，挪到对应的位置
for (int i = 0; i < list.size() - 1; ++i) {
// 判断列表list是否已经有序
boolean isFlag = true;
// 每一趟排序时，不断比较当前元素和下一个元素谁大，把大的元素往后挪
// 因为列表list的元素是数组int[]，数组的第二个元素保存的是军人数目，所以这里进行比较的元素是数组的第二个元素
for (int j = 0; j < list.size() - 1 - i; ++j) {
// 获取当前行标的军人数目
int before = list.get(j)[1];
// 获取下一行标的军人数目
int next = list.get(j + 1)[1];
if (before > next) {
// 若当前军人数目大于下一军人数目，交换两者对应的列表list的元素
int[] temp = list.get(j);
list.set(j, list.get(j + 1));
list.set(j + 1, temp);
// 出现交换，那么列表list还不是有序
isFlag = false;
}
}
if (isFlag) {
// 若列表list已经有序，结束循环
break;
}
}
// 定义结果数组nums，用来保存排序后的前k行军人数目
int[] nums = new int[k];
// 从0循环到k-1，构造结果数组nums
for (int i = 0; i < k; ++i) {
// 直接把排序后的列表list的行标赋值给结果数组nums
nums[i] = list.get(i)[0];
}
// 返回结果数组nums
return nums;
}
}
提交结果
执行用时5ms，时间击败6.90%的用户，内存消耗39.3MB，空间击败79.76%的用户。
方法2
方法1的执行用时太差了，方法2在方法1的基础上进行优化。
方法2改为用数组res来保存每行的军人数目和标号，用一个数字来保存两个信息，怎么保存？
通过军人数目 * 100 + 行标，再保存进数组里，再直接调用系统类的Arrays.sort方法来对数组排序，Arrays.sort的排序比方法1单纯地使用冒泡排序要高效，再把排序后的数组res的元素对100取余，就能获取到对军人数目排序后的行标。
为什么是乘以100？
因为题目里规定了矩阵的长度最大是100，那么军人数目最大就是100，行标最大就是99，军人数目都乘以100后，相对大小还是不变，这时再加上行标，因为最大行标是99，小于100，不会因为行标而导致相对大小改变，这里就能在军人数目的基础上再比较出行标的大小，如果不这样做，当不同行的军人数目相等时是无法比较出大小的。
解答代码
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
// 思路：使用数组统计每行的军人数目和行标，通过计算换算实现一个数字保存军人数目和行标，直接调用系统类排序方法进行排序，取排序后的前k个
// 定义战斗力数组res，长度为矩阵的行数
int[] res = new int[mat.length];
// 遍历矩阵mat的行
for (int i = 0; i < mat.length; ++i) {
// 获取矩阵mat的行
int[] row = mat[i];
// 定义军人数目，初始为0
int count = 0;
// 遍历每行的列
for (int col : row) {
if (1 == col) {
// 若元素是1，那么就是军人，军人数目加1
++count;
}
}
// 军人数目 * 100 + 行号，赋值到战斗力数组res中
res[i] = count * 100 + i;
}
// 对战斗力数组res进行排序
Arrays.sort(res);
// 定义结果数组nums，用来保存排序后的前k行军人数目
int[] nums = new int[k];
// 从0循环到k-1，构造结果数组nums
for (int i = 0; i < k; ++i) {
// 战斗力数组res的元素对100取余，赋值给结果数组nums的元素
nums[i] = res[i] % 100;
}
// 返回结果数组nums
return nums;
}
}
提交结果
执行用时1ms，时间击败98.36%的用户，内存消耗39.6MB，空间击败24.46%的用户。
可以看到，方法2相比方法1的执行用时大大节约了。
方法3
方法2还有可以优化的地方，方法3在方法2的基础上再进行优化。
统计每行的军人数目时还可以继续优化，改为通过二分查找法来统计，执行用时还可以再降。
题目说军人1必定在平民0之前，所以数组是有序的，使用二分查找法快速找出最后的1，最后的1对应的行标加1就是这行的军人数目。
这里使用二分查找法时，具体细节有点不同，不仅仅是查找等于某个值的元素，还要加上判断这个元素后面是否还有1，如果这个元素后面没有1了，那么就是找到了对应的元素，这个元素就是最后的1。
解答代码
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
// 思路：使用数组统计每行的军人数目和行标，统计时使用二分查找法，通过计算换算实现一个数字保存军人数目和行标，直接调用系统类排序方法进行排序，取排序后的前k个
// 定义战斗力数组res，长度为矩阵的行数
int[] res = new int[mat.length];
// 遍历矩阵mat的行
for (int i = 0; i < mat.length; ++i) {
// 获取矩阵mat的行
int[] row = mat[i];
// 定义左指针，初始为0
int left = 0;
// 定义右指针，初始为矩阵行的最后列标
int right = row.length - 1;
// 定义中间指针
int center;
// 定义军人数目是否为0的标记
boolean isZero = true;
// 二分查找法，不过具体细节有点不同，不仅仅是查找等于某个值的元素，还要加上判断这个元素后面是否还有1，如果这个元素后面没有1了，那么就是找到了对应的元素，这个元素就是最后的1，它的列标加1就是这行1的个数
while (left <= right) {
// 计算中间指针
center = (left + right) / 2;
if (1 == row[center]) {
// 若中间指针对应的元素等于1，判断它是否为最后的1
if (center == row.length - 1) {
// 若中间指针已经是最后行标了，那么它对应的元素是最后的1
// 军人数目 * 100 + 行号，赋值到战斗力数组res中
res[i] = (center + 1) * 100 + i;
// 军人数目不为0，标记设置为false
isZero = false;
break;
}
if (0 == row[center + 1]) {
// 若中间指针下一个行标的元素是0，那么它对应的元素也是最后的1
// 军人数目 * 100 + 行号，赋值到战斗力数组res中
res[i] = (center + 1) * 100 + i;
// 军人数目不为0，标记设置为false
isZero = false;
break;
}
// 它不是最后的1，二分数组，向右缩小查找，中间指针加1赋值给左指针
left = center + 1;
} else {
// 若中间指针对应的元素不等于1，直接二分数组，向左缩小查找，中间指针减1赋值给右指针
right = center - 1;
}
}
if (isZero) {
// 若军人数目为0，那么军人数目 * 100 + 行号 = 行号，赋值到战斗力数组res中
res[i] = i;
}
}
// 对战斗力数组res进行排序
Arrays.sort(res);
// 定义结果数组nums，用来保存排序后的前k行军人数目
int[] nums = new int[k];
// 从0循环到k-1，构造结果数组nums
for (int i = 0; i < k; ++i) {
// 战斗力数组res的元素对100取余，赋值给结果数组nums的元素
nums[i] = res[i] % 100;
}
// 返回结果数组nums
return nums;
}
}
提交结果
执行用时1ms，时间击败98.36%的用户，内存消耗39.6MB，空间击败12.81%的用户。
这里可能数据范围不够大，运行时间的差异不是很明显。
算法总结
有两个优化点：
1、保存军人数目和排序可以优化，通过军人数目 * 100 + 行标，排序，再对100取余，来代替原来的改造冒泡排序。
方法1需要使用列表，列表元素要用数组来保存军人数目和行标，再改造冒泡排序来排序军人数目，排序完成后再获取列表元素中的行标，构造成前k个行标。
方法2改为使用数组，数组首先就比列表节省时间和空间，而且抛弃了元素用数组来保存，这里又节约了时间和空间，通过军人数目 * 100 + 行标，再保存进数组里，再直接调用系统类的Arrays.sort方法来对数组排序，这里的效率又比方法1用冒泡排序要高效，因为Arrays.sort方法的排序是根据数组长度和有序程度挑选适合的排序方法进行排序的，比方法1单纯地使用冒泡排序是更高效的。
2、统计每行的军人数目可以优化，通过二分查找法来统计，而不是直接暴力遍历来统计。
方法1和方法2还是直接使用暴力遍历来统计每行的军人数目，这里的时间复杂度就是O(n)。
方法3优化为使用二分查找法来统计每行的军人数目，因为题目有说军人1必定在平民0之前，所以数组是有序的，所以可以用二分查找法来快速找出最后的1，从而计算出这行的军人数目，这里的时间复杂度就变成了O(logN)，比之前的时间复杂度O(n)降低了一个层级的数量级。
原文链接
原文链接：矩阵中战斗力最弱的K行