关键词

二分查找，Heap，PriorityQueue

题目描述

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/

Given a m * n matrix mat of ones (representing soldiers) and zeros (representing
 civilians), return the indexes of the k weakest rows in the matrix ordered from
 the weakest to the strongest.

A row i is weaker than row j, if the number of soldiers in row i is less than 
the number of soldiers in row j, or they have the same number of soldiers but
 i is less than j. Soldiers are always stand in the frontier of a row, 
that is, always ones may appear first and then zeros.

 

Example 1:

Input: mat = 
[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 
k = 3
Output: [2,0,3]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 2 
row 1 -> 4 
row 2 -> 1 
row 3 -> 2 
row 4 -> 5 
Rows ordered from the weakest to the strongest are [2,0,3,1,4]
Example 2:

Input: mat = 
[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 
k = 2
Output: [0,2]
Explanation: 
The number of soldiers for each row is: 
row 0 -> 1 
row 1 -> 4 
row 2 -> 1 
row 3 -> 1 
Rows ordered from the weakest to the strongest are [0,2,3,1]
 

Constraints:

m == mat.length
n == mat[i].length
2 <= n, m <= 100
1 <= k <= m
matrix[i][j] is either 0 or 1.

博主第一次提交的代码

我忽略了1的性质

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        int[] cache = new int[mat.length];
        for( int i = 0; i < mat.length; i++){
            int tmp = 0;
            for(int each: mat[i]){
                tmp+=each;
            }
            cache[i] = tmp;
        }
        int[] result = new int[k];
        for(int i = 0; i < k; i++){
            result[i] = findMin(cache);
        }
        return result;
        
    }
    public int findMin(int[] input){
        int min = Integer.MAX_VALUE;
        int index = -1;
        for(int i = 0; i < input.length; i++){
            if(input[i] < min){
                min = input[i];
                index = i;
            }
        }
        input[index] = Integer.MAX_VALUE;
        return index;
    }
}

其他人优秀的代码

https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix/discuss/496555/Java-Best-Solution-100-TimeSpace-Binary-Search-%2B-Heap

class Solution {
    public int[] kWeakestRows(int[][] mat, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
        int[] ans = new int[k];
        
        for (int i = 0; i < mat.length; i++) {
            pq.offer(new int[] {numOnes(mat[i]), i});
            if (pq.size() > k)
                pq.poll();
        }
        
        while (k > 0)
            ans[--k] = pq.poll()[1];
        
        return ans;
    }
    
    private int numOnes(int[] row) {
        int lo = 0;
        int hi = row.length;
        
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            
            if (row[mid] == 1)
                lo = mid + 1;
            else
                hi = mid;
        }
        
        return lo;
    }
}