1337. 矩阵中战斗力最弱的 K 行
思路：
此题有两种方法：朴素和 二分+优先队列
朴素的很简单，用一个二元数组记录每一行战力和index 然后 自定义一个Arrays.sort()按照值优先其次是index来排序
由于军人在前面，所以可以用二分来查找右边的最后一个军人的下标，由于存在没有军人的情况，所以需要额外判断下下标在哪里。之后用大根堆来存储二元数组，并且更新当前的最大值。最后堆顶弹出并从右往左放入数组即可：
代码如下：
<![CDATA[
class Solution {
public int[] kWeakestRows(int[][] mat, int k) {
// // 朴素sort
// int n = mat.length;
// int m = mat[0].length;
// int[][] sol = new int[n][2];
// for(int i=0; i<n;i++){
// int count = 0;
// for(int j=0; j<m;j++){
// if(mat[i][j]==1) count ++;
// }
// sol[i] = new int[]{i, count};
// }
// Arrays.sort(sol, (a,b)-> {
// if(a[1]!=b[1]) return a[1]-b[1];
// else return a[0]-b[0];
// });
// int[] ans = new int[k];
// for (int i = 0; i < k; i++) ans[i] = sol[i][0];
// // System.out.println(Arrays.toString(sol[0]));
// return ans;
// 大根堆：
int n = mat.length;
int m = mat[0].length;
PriorityQueue<int []> q = new PriorityQueue<int[]>(
(a,b)->{
if(a[0]!=b[0]) return b[0]-a[0];
return b[1]-a[1];
}
);
// 二分查找最右边的下标
for(int i=0; i<n; i++){
int l = 0, r = m-1;
while(l<r){
int mid = l+r+1>>1;
if(mat[i][mid]==1) l = mid;
else r = mid-1;
}
int cur_idx = mat[i][r]==1 ? r+1:r;
// System.out.println(i+" "+cur_idx);
if(q.size()==k && q.peek()[0] > cur_idx) q.poll();
if(q.size()<k) q.add(new int[]{cur_idx,i});
}
int[] ans = new int[k];
int idx = k - 1;
while(!q.isEmpty()) ans[idx--] = q.poll()[1];
return ans;
}
}
]]>
