LeetCode（Heap)1337. The K Weakest Rows in a Matrix

清疚 2023-09-24 23:36 20阅读 0赞

# 1.问题 #

You are given an m x n binary matrix mat of 1’s (representing soldiers) and 0’s (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1’s will appear to the left of all the 0’s in each row.

A row i is weaker than a row j if one of the following is true:

The number of soldiers in row i is less than the number of soldiers in row j.  
Both rows have the same number of soldiers and i < j.  
Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

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 in each row is:
> 
>  *  Row 0: 2
>  *  Row 1: 4
>  *  Row 2: 1
>  *  Row 3: 2
>  *  Row 4: 5  
>     The rows ordered from weakest to 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 in each row is:
> 
>  *  Row 0: 1
>  *  Row 1: 4
>  *  Row 2: 1
>  *  Row 3: 1  
>     The rows ordered from weakest to 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.

# 2. 解题思路 #

## 方法1： ##

> 用行索引标记分数  
> 我们可以定义 score =j+i 或 score=j + i/rows，但是，如果 i 太大而 j 太小，我可能比 j 有更大的影响。 如果我们使用 score= j + i/rows，i/rows 是一个浮点数，很难排序，所以两边都乘以 rows 得到 rowscore= j\*rows+i

## 方法2： ##

>  *  使用了PriorityQueue数据结构，其中PriorityQueue是一种基于优先级的队列，可以按照元素的优先级进行排序，并保证每次从队列中取出的元素都是优先级最高（或最低）的元素。
>  *  优先级被定义为“军队的战斗力和行的索引值”，即先根据战斗力排序，如果战斗力相同则按照行的索引值排序。

>  *  首先，将每一行的战斗力和行号组成一个int数组加入PriorityQueue，即数组第一个元素为该行的战斗力，第二个元素为该行的索引号。由于PriorityQueue默认是小根堆，所以可以直接使用a\[0\] != b\[0\] ? a\[0\] - b\[0\] : a\[1\] - b\[1\]作为比较器，实现先根据战斗力排序，如果战斗力相同则按照行的索引值排序。
>  *  然后，将PriorityQueue中的前k个元素取出来，这k个元素的索引号即为最弱的k个行的索引号。
>  *  最后，将这k个索引号放到一个数组中并返回。

## 方法3： ##

> 首先对矩阵每一行中士兵的数量进行计数  
> 然后进行k次线性搜索，每次找到数量最小的行的索引  
> 并将其加入结果数组中，直到结果数组填满为止。  
> 该方法的时间复杂度为O(m \* n \* k)，其中m和n分别为矩阵的行数和列数。

## 方法4 ##

>  *  遍历二维数组mat，统计每一行中的1的数量count，以及该行的行数i，并将其存储在一个HashMap中，键为行数i，值为1的数量count。
>  *  将HashMap中的键值对存储在一个LinkedList中，并通过Collections.sort方法，按值升序排序。
>  *  从LinkedList中取出前k个键值对中的键，存储在一个数组中，并返回该数组。  
>     时间复杂度为O(mn log mn)，其中m和n分别为mat的行数和列数。主要时间开销在排序操作。

# 3. 代码 #

## 代码1： ##

解释：  
为什么是`temp[i]=j * rows + i`, `temp[i]=temp[i]%rows;`

即使两排都有相同的士兵，但上排将被视为较弱的一排.所以乘以 rows 肯定会保持顶层 总是小于底层行

class Solution {
        
        public int[] kWeakestRows(int[][] mat, int k) {
        
             int rows= mat.length; // 获取矩阵行数
            int[] score = new int[rows]; // 定义存储每行得分的数组
            for (int i = 0; i < rows; i++) {
        
                int j=0;
                // 遍历每一行，查找第一个值为0的位置j
                for( j = 0; j<mat[i].length ; j++){
        
                    if(mat[i][j]==0) break;
                }
                // 每行得分为：0的位置之前的元素个数*行数+当前行号i
                score[i]=j * rows + i;
            }
            // 对得分数组进行排序
            Arrays.sort(score);
            for (int i = 0; i < score.length; i++) {
        
                score[i]= score[i]%rows; // 取模得到当前行号
            }
            // 返回前k个最弱行的行号数组
            return  Arrays.copyOfRange(score, 0, k);
        }
    }

## 代码2： ##

class Solution {
        
      public int[] kWeakestRows(int[][] mat, int k) {
        
    		// 创建一个基于数组的小根堆，每个元素为一个数组，第一项为1的数量，第二项为行号
    		PriorityQueue<int[]> q = new PriorityQueue<>(
    		(a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]
    		);
    		// 计算每行1的数量，并将其加入小根堆
    		int pos=0;
    		for (int[] row : mat){
        
    			int lo = 0, hi = row.length;
    			while(lo < hi){
        
    				int mid = (lo + hi) / 2;
    				if (row[mid] != 0) lo = mid + 1;
    				else hi = mid;
    			}
    			q.add(new int[]{
        lo, pos++});
    		}
    		// 从小根堆中取出前k个元素的行号
    		int[] output = new int[k];
    		for(int i = 0; i < k; i++) output[i] = q.remove()[1];
    		return output;
    		}
    }

解释：

//PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[1]-b[1]);
            PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
        
                @Override
                public int compare(int[] o1, int[] o2) {
        
                    return o1[0]-o2[0];
                }
            });

## 代码3： ##

public int[] kWeakestRows4(int[][] mat, int k) {
        
        // 创建一个长度为矩阵列数加一的List数组，用来存储每个数量的矩阵行数，方便后面统计结果
        List<Integer>[] map = new List[mat[0].length + 1];
        // 对矩阵每行的soldiers数量以map的下标进行排列，如map[0]中要保存的是0个soldier的矩阵行数
        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 {
        
                    break;
                }
            }
            // temp作为临时变量，用来辅助map保存对应数量的矩阵行数
            List<Integer> temp = map[count];
            if(temp == null) {
        
                temp = new ArrayList();
                map[count] = temp;
            }
            temp.add(i);
        }
        // 创建结果数组
        int[] result = new int[k];
        // 循环遍历每个数量的矩阵行数，从小到大统计到达k个为止
        int i = 0;
        int j = 0;
        while(i < k) {
        
            // 跳过null的行
            while(map[j] == null) j++;
            // 保存数量为j的行
            List<Integer> temp = map[j++];
            for(int t = 0; t < temp.size() && i < k; t++, i++) {
        
                result[i] = temp.get(t);                
            }
        }
        // 返回结果数组
        return result;
    }
    
        }

> 解题思路基本相同

class Solution {
        
        public int[] kWeakestRows(int[][] mat, int k) {
        
            int[] result = new int[k];
    
         //收集士兵计数到一维数组（每行）
            int[] counts = new int[mat.length];
            for (int i = 0; i < mat.length; i++) {
        
                for (int j = 0; j < mat[i].length; j++) {
        
                    if (mat[i][j] == 1) {
        
                        counts[i]++;
                    }
                }
            }
    
            int indexer = 0;
            while (k > 0) {
        
         //进行k次线性搜索，取最小索引值填充结果数
                int minIndex = 0;
                for (int i = 0; i < counts.length; i++) {
        
                    if (counts[i] < counts[minIndex]) {
        
                        minIndex = i;
                    }
                }
    
                result[indexer++] = minIndex;
                counts[minIndex] = Integer.MAX_VALUE;
                k--;
            }
    
            return result;
        }
    }

class Solution {
        
        public int[] kWeakestRows(int[][] mat, int k) {
        
            int[] result = new int[k];
    
            // 收集士兵计数到一维数组（每行）
            int[] counts = new int[mat.length];
            for (int i = 0; i < mat.length; i++) {
        
                for (int j = 0; j < mat[i].length; j++) {
        
                    if (mat[i][j] == 1) {
        
                        counts[i]++;
                    }
                }
            }
    
            int indexer = 0;
            while (k > 0) {
        
                // 进行k次线性搜索，取最小索引值填充结果数
                int minIndex = 0;
                for (int i = 0; i < counts.length; i++) {
        
                    if (counts[i] < counts[minIndex]) {
        
                        minIndex = i;
                    }
                }
    
                result[indexer++] = minIndex;
                counts[minIndex] = Integer.MAX_VALUE;
                k--;
            }
    
            return result;
        }
    }

## 方法4 ##

class Solution {
        
        public int[] kWeakestRows(int[][] mat, int k) {
        
            // 创建一个Map，保存每行的索引和1的数量
            Map<Integer,Integer> map=new HashMap<>();
            // 创建一个数组来保存结果
            int res[]=new int[k];
            // 遍历矩阵，将每行的士兵数存入map
            for(int i=0;i<mat.length;i++){
        
                int count=0;
                for(int j=0;j<mat[i].length;j++){
        
                    if(mat[i][j]==1)
                        count++;
                    else break;
                }
                map.put(i,count);
            }
            
            // 对map进行排序
            List<Map.Entry<Integer,Integer>> list=new LinkedList<Map.Entry<Integer,Integer>>(map.entrySet());
            Collections.sort(list,new Comparator<Map.Entry<Integer,Integer>>(){
        
                public int compare(Map.Entry<Integer,Integer> a,Map.Entry<Integer,Integer> b){
        
                    if(a.getValue()==b.getValue())
                        return a.getKey()-b.getKey();
                    return a.getValue()-b.getValue();
                }
            });
            
            // 将排序后的结果存入res数组中
            int i=0;
            for(Map.Entry<Integer,Integer> mp:list)
            {
        
                res[i++]=mp.getKey();
                if(i==k)
                    break;
            }
            return res;
        }
    }