刷力扣练习JAVA
力扣1337.矩阵中战斗力最弱的K行
题目：
给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
链接：https://leetcode-cn.com/problems/the-k-weakest-rows-in-a-matrix
分析
二分检索+堆栈
解答代码：JAVA
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
int m=mat.length,n=mat[0].length;
List<int[]>power =new ArrayList<int[]>();//power记录每一行的1个数
for(int i=0;i<m;i++)
{
int j=0,l=n-1,pos=-1;//初始化pos记录1个数
while(j<=l)
{
int mid=(j+l)/2;
if(mat[i][mid]==0)//二分法判断中间是否为0
{
l=mid-1;
}
else
{
j=mid+1;//是1
pos=mid;
}
}
power.add(new int []{pos+1,i});
}
PriorityQueue<int[]>pq=new PriorityQueue<int[]>(new Comparator<int[]>()
{
public int compare(int []pair1,int[] pair2)
{
if(pair1[0]!=pair2[0])
{
return pair1[0]-pair2[0];
}
else
{
return pair1[1]-pair2[1];
}
}
});
for(int[]pair:power)
{
pq.offer(pair);
}
int[]ans=new int[k];
for(int i=0;i<k;i++)
{
ans[i]=pq.poll()[1];
}
return ans;
}
}
?
