美团点评2019春招后台开发方向笔试算法题第一题：黑白矩阵
分享一下我的代码，顺便希望大家帮忙看看还有没有问题。也可以到我的博客查看这篇文章，包含题目描述：https://52heartz.top/articles/algorithm-black-white-matrix/
思路
把矩阵看作像国际象棋棋盘一样的黑白矩阵。最终的目的就是要黑格子中的数字相同，白格子中的数字相同。同时我们希望用最少的修改次数使矩阵变成这种状态。
分别统计黑格子和白格子中出现最多的数字和第二多的数字以及出现的次数。
如果黑格子中出现最多的数字和白格子中出现最多的数字不一样，那么只需要分别把黑白格子中除了出现最多的数字以外的其他数字改为和出现最多的数字相同。就可以达到满足题意的状态，而且这种方法修改的次数是最少的。再具体一点就是使用矩阵的大小减去黑白格子中出现最多的数字的个数，也就是减去不需要修改的数，剩下的就是需要修改的数字的个数。
如果黑格子中出现最多的数字和白格子中出现最多的数字一样。那么就要考虑出现第二多的数字了。那么这个时候可能有两种组合，
组合1：黑格子中出现最多的数字的个数和白格子中出现第二多的数字的个数相加
组合2：白格子中出现最多的数字的个数和黑格子中出现第二多的数字的个数相加
这个组合的数就是不需要修改的数的个数，哪个组合的数更大，就说明这个组合需要修改的数更少。所以用矩阵的大小减去更大的组合数，就是最少需要修改的次数。
代码
代码不是当时用于提交的代码，把输入流绑定到了文件输入流方便本地测试，大家也可以使用后边的测试用例测试一下。
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;
}
}
}
}
测试用例
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
对于这几个测试用例，我的程序的运行结果是
4 4 0 8 8 9
#美团##春招##笔试题目##笔经#
投递美团等公司10个岗位
度小满一面6人在聊
