算法题：黑白矩阵

发表于 | 更新于 | 阅读次数：

一道美团笔试题。

2019年4月24日，美团点评2019春招后台开发方向笔试算法题。

题目

我们称一个矩阵为黑白矩阵，当且仅当对于该矩阵中每一个位置如 (i,j)，其上下左右四个方向的数字相等，即(i-1,j)，(i+1,j)，(i,j+1)，(i,j-1)四个位置上的数字两两相等且均不等于 (i,j) 位置上的数字。（超出边界的格子忽略）

现在给出一个 n*m 的矩阵，我们想通过修改其中的某些数字，使得该矩阵成为黑白矩阵，问最少修改多少个数字。

输入

第一行包含两个整数n，m，表示矩阵的长宽。（1≤n,m≤100000,1≤n*m≤100000）

接下来有n行，每行包含m个整数，中间用空格隔开，表示 n*m 的矩阵。

输出

输出仅包含一个数字，表示该矩阵想修改为黑白矩阵最少修改的数字数量。

样例1

输入

1
2
3
4
3 3
1 1 1
1 1 1
1 1 1

输出

1
4

样例2

输入

1
2
3
4
3 3
1 1 1
1 5 1
1 1 1

输出

1
4

解答1[Java]：

核心思想

把矩阵看作像国际象棋棋盘一样的黑白矩阵。最终的目的就是要黑格子中的数字相同，白格子中的数字相同。同时我们希望用最少的修改次数使矩阵变成这种状态。

分别统计黑格子和白格子中出现最多的数字和第二多的数字以及出现的次数。

如果黑格子中出现最多的数字和白格子中出现最多的数字不一样，那么只需要分别把黑白格子中除了出现最多的数字以外的其他数字改为和出现最多的数字相同。就可以达到满足题意的状态，而且这种方法修改的次数是最少的。再具体一点就是使用矩阵的大小减去黑白格子中出现最多的数字的个数，也就是减去不需要修改的数，剩下的就是需要修改的数字的个数。

如果黑格子中出现最多的数字和白格子中出现最多的数字一样。那么就要考虑出现第二多的数字了。那么这个时候可能有两种组合，

组合1：黑格子中出现最多的数字的个数和白格子中出现第二多的数字的个数相加

组合2：白格子中出现最多的数字的个数和黑格子中出现第二多的数字的个数相加

这个组合的数就是不需要修改的数的个数，哪个组合的数更大，就说明这个组合需要修改的数更少。所以用矩阵的大小减去更大的组合数，就是最少需要修改的次数。

代码

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
92
93
94
95
96
97
98
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        File file = new File("test_case_1.txt");
        try {
            FileInputStream fileInputStream = new FileInputStream(file);
            System.setIn(fileInputStream);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        }

        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            HashMap<Integer, Integer> blackCounterMap = new HashMap<>();
            HashMap<Integer, Integer> whiteCounterMap = new HashMap<>();

            int columns = sc.nextInt();
            int rows = sc.nextInt();
            int elementNum = rows * columns;

            int inputTemp = 0;
            for (int i = 0; i < rows; ++i) {
                for (int j = 0; j < columns; ++j) {
                    inputTemp = sc.nextInt();
                    // i + j为偶数看作黑格子，i + j为奇数，看作白格子
                    if (((i + j) & 1) == 0) {
                        if (blackCounterMap.containsKey(inputTemp)) {
                            blackCounterMap.put(inputTemp, blackCounterMap.get(inputTemp) + 1);
                        } else {
                            blackCounterMap.put(inputTemp, 1);
                        }
                    } else {
                        if (whiteCounterMap.containsKey(inputTemp)) {
                            whiteCounterMap.put(inputTemp, whiteCounterMap.get(inputTemp) + 1);
                        } else {
                            whiteCounterMap.put(inputTemp, 1);
                        }
                    }
                }
            }

            // 第一个下标区分元素出现次数最多和第二多，0代表最多，1代表第二多
            // 第二个下标区分 key 和 value，0代表key，1代表value
            // blackMax[0][0] 黑格子中出现次数最多的元素
            // blackMax[0][1] 黑格子中出现次数最多的元素出现的次数
            // blackMax[1][0] 黑格子中出现次数第二多的元素
            // blackMax[1][1] 黑格子中出现次数第二多的元素出现的次数
            // whiteMax数组和blackMax数组类似
            int[][] blackMax = new int[2][2];
            int[][] whiteMax = new int[2][2];

            findMaxAndSecondMax(blackCounterMap, blackMax);
            findMaxAndSecondMax(whiteCounterMap, whiteMax);

            // 如果黑格子中出现次数最多的和白格子中出现最多的数字不一样，那么就
            // 用元素总数减去这两个数，把不是出现最多的数字改为相应的数字即可
            int result = 0;
            if (blackMax[0][0] != whiteMax[0][0]) {
                result = elementNum - blackMax[0][1] - whiteMax[0][1];
            } else {
                int combination1 = blackMax[0][1] + whiteMax[1][1];
                int combination2 = blackMax[1][1] + whiteMax[0][1];
                if (combination1 > combination2) {
                    result = elementNum - combination1;
                } else {
                    result = elementNum - combination2;
                }
            }
            System.out.println(result);
        }
    }

    /**
     * 从countermap中找出出现次数最多和第二多的数和出现的次数，存到max数组中
     * @param countermap
     * @param max
     */
    private static void findMaxAndSecondMax(HashMap<Integer, Integer> countermap, int[][] max) {
        for (Map.Entry<Integer, Integer> entry : countermap.entrySet()) {
            int maxTemp = entry.getValue();
            if (maxTemp > max[0][1]) {
                max[1][0] = max[0][0];
                max[1][1] = max[0][1];
                max[0][0] = entry.getKey();
                max[0][1] = maxTemp;
            } else if (maxTemp > max[1][1]) {
                max[1][0] = entry.getKey();
                max[1][1] = maxTemp;
            }
        }
    }
}

测试用例

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
3 3
1 1 1
1 1 1
1 1 1

3 3
1 1 1
1 5 1
1 1 1

4 4
1 2 1 2
2 1 2 1
1 2 1 2
2 1 2 1

4 4
1 2 3 4
2 1 4 3
1 2 3 4
2 1 4 3

4 4
1 2 3 3
2 1 3 3
1 2 3 3
2 1 3 3

4 4
1 5 3 3
2 6 3 3
8 2 3 3
2 7 3 3

结果

对于上边的测试用例，执行结果为：

1
2
3
4
5
6
4
4
0
8
8
9