一定要早日上岸鸭 · August 1, 2021 0

1337. 矩阵中战斗力最弱的 K 行

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<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; } }