【力扣-1337打卡】

package com.example.demomain.demoleetcode.easy;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
 * 

 * 请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
 * 

 * 如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
 * 

 * 军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
 * 

 * 示例 1：
 * 

 * 输入：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
 * 输出：[2,0,3]
 * 解释：
 * 每行中的军人数目：
 * 行 0 -> 2
 * 行 1 -> 4
 * 行 2 -> 1
 * 行 3 -> 2
 * 行 4 -> 5
 * 从最弱到最强对这些行排序后得到 [2,0,3,1,4]
 * 示例 2：
 * 

 * 输入：mat =
 * [[1,0,0,0],
 * [1,1,1,1],
 * [1,0,0,0],
 * [1,0,0,0]],
 * k = 2
 * 输出：[0,2]
 * 解释：
 * 每行中的军人数目：
 * 行 0 -> 1
 * 行 1 -> 4
 * 行 2 -> 1
 * 行 3 -> 1
 * 从最弱到最强对这些行排序后得到 [0,2,3,1]
 * 提示：
 * 

 * m == mat.length
 * n == mat[i].length
 * 2 <= n, m <= 100
 * 1 <= k <= m
 * matrix[i][j] 不是 0 就是 1
 *
 * @author Administrator
 */
public class KWeakestRows {
    public int[] kWeakestRowsByStream(int[][] mat, int k) {
        //比如我们计划向HashMap中放入7个元素的时候，我们通过expectedSize / 0.75F + 1.0F计算，7/0.75 + 1 = 10 ,10经过JDK处理之后，会被设置成16，这就大大的减少了扩容的几率。
        int length = mat.length;
        Map<Integer, Integer> matMap = new HashMap<>(length / 3 * 4 + 1);
        for (int i = 0; i < length; i++) {
            int sum = Arrays.stream(mat[i]).sum();
            matMap.put(i, sum);
        }

        return matMap
                .entrySet()
                .stream()
                // 先根据战斗力排序，再根据行号排序
                .sorted(Comparator.<Map.Entry<Integer, Integer>>comparingInt(Map.Entry::getValue).thenComparing(Map.Entry::getKey))
                // 取 k 位
                .limit(k)
                // 取行号
                .mapToInt(Map.Entry::getKey)
                .toArray();
    }

    @Test
    public void test() {
        int[][] mat = {{1, 0, 0, 0}, {1, 1, 1, 1}, {1, 1, 0, 0}, {1, 1, 0, 0}};
        Arrays.stream(kWeakestRowsByStream(mat, 3)).forEach(System.out::println);
    }
}

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91