请听第二道算法题：修改矩阵

今天来看一下美团2019春招的第二道算法题。

image

首先还是分析一下题目的规律。

根据题意，每个格子e的上下左右四个相邻元素必须相等，且不等于e。

我们定义一个概念：当格子的横纵坐标之和为奇数时我们称该格子为奇数格子，当格子的横纵坐标之和为偶数时我们称该格子为偶数格子。

我们可以发现，对于满足题意的矩阵，所有偶数格子上的数均相等，所有奇数格子上的数均相等，且奇数格子上的数不等于偶数格子上的数。

若要求总的修改的数字数量最少，等价于转换为保留出现次数最多的数字，我们可以分解为奇数格子上保留出现次数最多的数字，同时偶数格子上也保留出现次数最多的数字。

当然还必须保证奇数格子上保留的数字不能等于偶数格子上保留的数字。

我们约定将ni出现的次数ci记为（ni, ci）的形式。

我们考虑最一般的情况，即奇数格子上至少有两种不同的数字，偶数格子上也是至少有两种不同的数字。

我们把奇数格子上的数按出现次数从大到小排序，得到（n1，c1），（n2，c2）。。。

我们把偶数格子上的数按出现次数从大到小排序，得到（m1，d1），（m2，d2）。。。

如果n1 != m1，那么保留n1和m1一定就是最优解；如果n1==m1，就有两种方案可以选择，一是保留n1和m2，二是保留n2和m1，总之，最优解一定在保留n1和m1、保留n1和m2或保留n2和m1中产生。

但是在写代码时这样去判断的话会增加复杂性，在代码中可以直接两重循环，判断在保留n1和m1、n1和m2、n2和m1、n2和m2时，保留的数字数量，取最大值即可。两重循环时多考虑了保留n2和m2这种情况，多考虑一种情况不影响最终的结果。

上golang代码：

package main

import (
  "bufio"
  "fmt"
  "os"
  "sort"
  "strconv"
  "strings"
)

type pair struct {
  num int
  cnt int
}

type PairList []pair

func (p PairList) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }
func (p PairList) Len() int           { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].cnt > p[j].cnt }

func main() {
  nr := bufio.NewReader(os.Stdin)
  nm, _ := nr.ReadString('\n')
  nm = strings.Trim(nm, "\r\n")
  n, _ := strconv.Atoi(strings.Split(nm, " ")[0])
  m, _ := strconv.Atoi(strings.Split(nm, " ")[1])
  odde := make(map[int]int) //统计奇数格子上各数字出现的次数
  evene := make(map[int]int)//统计偶数格子上各数字出现的次数
  for i := 0; i < n; i++ {
    str, _ := nr.ReadString('\n')
    str = strings.Trim(str, "\r\n")
    line := strings.Split(str, " ")

    for j := 0; j < m; j++ {
      e, _ := strconv.Atoi(line[j])
      if (i+j)%2 == 0 {
        cnt, ok := odde[e]
        if !ok {
          odde[e] = 1
        } else {
          odde[e] = cnt + 1
        }
      } else {
        cnt, ok := evene[e]
        if !ok {
          evene[e] = 1
        } else {
          evene[e] = cnt + 1
        }
      }
    }
  }
  oddlist := make(PairList, 0, len(odde))
  for n, c := range odde {
    oddlist = append(oddlist, pair{n, c}) // 将map中的kv对封装成pair结构体，用于排序
  }
  sort.Sort(oddlist)
  if len(oddlist) == 1 {
      oddlist = append(oddlist, pair{-1, 0})
  }

  evenlist := make(PairList, 0, len(evene))
  for n, c := range evene {
    evenlist = append(evenlist, pair{n, c})
  }
  sort.Sort(evenlist)
  if len(evenlist) == 1 {
      evenlist = append(evenlist, pair{-1, 0})
  }

  var retained int // 保留的数字数量，取最大
  for i := 0; i < 2; i++ {
    for j := 0; j < 2; j++ {
      if oddlist[i].num != evenlist[j].num {
        retained = max(retained, oddlist[i].cnt + evenlist[j].cnt)
      }
    }
  }

  fmt.Println(n*m - retained)
}

func max(a, b int) int {
  if a > b {
    return a
  } else {
    return b
  }
}

实现代码的时候有一个细节需要注意：

因为前面在分析的时候，假设了n2和m2均存在，但是实际上n2或m2可能不存在，即奇数格子或偶数格子上只有一种数字。

所以在代码中的60行和69行，需要判断list长度是否为1，如果是，则填充一个pair{num:-1, cnt:0}。

可以验证，这种处理方式是能够保证准确结果的，并且提交代码也ac了:)

欢迎关注博主个人微信公众号~~~

image