1337. 矩阵中战斗力最弱的 K 行
思路:
此题有两种方法:朴素和 二分+优先队列
朴素的很简单,用一个二元数组记录每一行战力和index 然后 自定义一个Arrays.sort()按照值优先其次是index来排序
由于军人在前面,所以可以用二分来查找右边的最后一个军人的下标,由于存在没有军人的情况,所以需要额外判断下下标在哪里。之后用大根堆来存储二元数组,并且更新当前的最大值。最后堆顶弹出并从右往左放入数组即可:
代码如下:
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 {
// 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 q = new PriorityQueue(
(a,b)->{
if(a[0]!=b[0]) return b[0]-a[0];
return b[1]-a[1];
}
);
// 二分查找最右边的下标
for(int i=0; i>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()