The K Weakest Rows in a Matrix
给一个2d数组, 只有1和0, 问每一行1和0差最小的k个行号. 这个题我就按题意写了, 我看答案比我的快一点, 用的是binary search找1的个数..这个最差情况(full with 1)没区别…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
class Solution { public int[] kWeakestRows(int[][] mat, int k) { int[] res = new int[k]; PriorityQueue<String> q = new PriorityQueue<>(new Comparator<String>() { @Override public int compare(String o1, String o2) { int k1 = Integer.valueOf(o1.split("#")[0]); int k2 = Integer.valueOf(o2.split("#")[0]); int v1 = Integer.valueOf(o1.split("#")[1]); int v2 = Integer.valueOf(o2.split("#")[1]); if(v1 != v2) return v1 - v2; else return k1 - k2; } }); for(int i = 0; i < mat.length; i++) { int count = 0; for(int j = 0; j < mat[0].length; j++) { if(mat[i][j] == 1) count ++; else continue; } q.add(i+"#"+count); } for(int i = 0; i < k; i++) { String s = q.poll(); int v = Integer.valueOf(s.split("#")[0]); res[i] = v; } return res; } } |