美团点评春招在线笔试后台开发方向笔试题编程题第一题题解

题目概述：
定义一个矩阵为黑白矩阵，当且仅当对于矩阵内的任意一个元素，其上下左右的数字完全一致（如果存在）且不和本身重复
现给出一个矩阵A，给定大小为n*m，内部数据都为整型，请问至少修改矩阵中的几个元素才能使得矩阵A为黑白矩阵？
输入描述：
第一行：n m
之后n行，每行有m个整数，用空格分割
输出描述：
一个整数
输入样例：
3 3
1 1 1
1 1 1
1 1 1
输出样例：
4
输入样例2：
3 3
1 1 1
1 5 1
1 1 1
输出样例2：
4
输入样例3：
3 4
1 2 3 1
2 3 1 2
3 1 2 3
输出样例3：
6

import java.util.*;

public class TestMain {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        Map<Integer,Integer> map0 = new HashMap<>();
        Map<Integer,Integer> map1 = new HashMap<>();
        int[][] arr = new int[n][m];
        for(int i = 0; i<n;i++){
            for(int j = 0;j<m;j++){
                arr[i][j]= sc.nextInt();
            }
        }
        for(int i = 0; i<n;i++){
            for(int j = 0;j<m;j++){
                int target = arr[i][j];
                if((i+j)%2==0){
                    int count = 1;
                    if(map0.get(target)!=null){
                        count = map0.get(target)+1;
                    }else{

                    }
                    map0.put(target,count);
                }else{
                    int count = 1;
                    if(map1.get(target)!=null){
                        count = map1.get(target)+1;
                    }else{

                    }
                    map1.put(target,count);
                }
            }
        }
        List <Topnum> list = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry:map0.entrySet()){
            Topnum topnum = new Topnum();
            topnum.setKey(entry.getKey());
            topnum.setValue(entry.getValue());
            list.add(topnum);
        }
        list.sort(Comparator.comparingInt(Topnum::getValue));

        List <Topnum> list1 = new ArrayList<>();
        for(Map.Entry<Integer,Integer> entry:map1.entrySet()){
            Topnum topnum = new Topnum();
            topnum.setKey(entry.getKey());
            topnum.setValue(entry.getValue());
            list1.add(topnum);
        }
        list1.sort(Comparator.comparingInt(Topnum::getValue));
        if(list.get(list.size()-1).getKey().equals(list1.get(list1.size()-1).getKey())){
            int left = 0;
            int right = 0;
            if(list1.size()>1){
                left = (m*n+1)/2-list.get(list.size()-1).getValue()+(m*n)/2-list1.get(list1.size()-2).getValue();
            }else{
                left = (m*n+1)/2-list.get(list.size()-1).getValue()+(m*n)/2;
            }
            if(list.size()>1){
                right = (m*n+1)/2-list.get(list.size()-2).getValue()+(m*n)/2-list1.get(list1.size()-1).getValue();
            }else{
                right = (m*n+1)/2+(m*n)/2-list1.get(list1.size()-1).getValue();
            }
            System.out.println(left>right?right:left);
        }else{
            int ret1 = (m*n+1)/2-list.get(list.size()-1).getValue()+(m*n)/2-list1.get(list1.size()-1).getValue();
            System.out.println(ret1);
        }
    }
}
class Topnum {
    private Integer key;
    private Integer value;

    public Integer getKey() {
        return key;
    }

    public Integer getValue() {
        return value;
    }

    public void setKey(Integer key) {
        this.key = key;
    }

    public void setValue(Integer value) {
        this.value = value;
    }
}