主要用于交流思考
1.修改矩阵
时间限制：C/C++语言 1000MS；其他语言 3000MS内存限制：C/C++语言 65536KB；其他语言 589824KB题目描述：我们称一个矩阵为黑白矩阵，当且仅当对于该矩阵中每一个位置如(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的矩阵。输出输出仅包含一个数字，表示该矩阵想修改为黑白矩阵最少修改的数字数量。样例输入3 31 1 11 1 11 1 1样例输出4提示补充样例输入样例23 31 1 11 5 11 1 1输出样例24
我的思路：
题中说n行m列，按照我个人习惯，颠倒了一下
直接用暴力去解。行m，列n
1.从第0行开始，将该行的每个值逐个交替的存入字典a,b，键为该值，值为该值出现的次数。
若是偶数行（索引从0开始），则存入顺序为字典a,b；否则为b,a.且最终a中值的总和与b中值的总和总是差1，且总和为m*n。
2.将字典按照值逆序排序，也就是出现次数多的键排在前面。
3.两个for循环（本来以为很耗时，其实还行）逐个比较目前出现次数最大的键。
4.如果两个键不同，修改的次数，直接以m*n-v(k1)-v(k2)来计算。意思是，键不同且目前出现次数为最高，只需要将剩余不同的键分别修改为当前键即可。
例如：
1 3 1 3 1 31 1 3
在该矩阵中，字典a为:{'1':4,'3':1},字典b为{'3':3,'1':1}。按照我的思路来说，即出现次数最高的键不同，则只需将a中不为1的键修改为1，b中不为3的值修改为3。即最少修改次数是3*3-4-3=2。直接返回。
5.如果出现次数最高的键相同，则比较出现次数，此时考虑6,7两种情况。
6.此时该矩阵中仅有一个数字，例如全1，此时做比较的两个出现次数值的和即为m*n，那么将出现次数较小的值记为修改次数。参考样例1
7.此时该矩阵中有两个及上数字，比较v(k1)和v(k2)，保留当前较大值，取另一组的次大值，循环4-7。
求批评指正，修改
代码：
# m,n# matrix1 raw col# a_dict# b_dict# num"""该段为题目中的标准输入，每行读取，并存入矩阵"""m,n = map(int ,input().split(' '))matrix = []raw = []for i in range(m):raw = [x for x in input().split(' ')]matrix.append(raw)#print(m,n)#print(matrix)# i=(0,0) or i=(0,1)a_dict = {}b_dict = {}"""该段为测试，建立随机数大矩阵，和元矩阵。并记录不同过程的时间"""import numpy as npimport timematrix = np.random.randint(0,10,size=[1,100000])#matrix = np.ones((1000,100))m = 1n =100000"""该段为字典更新，其中以行为外循环，列以每2步一个循环，每次确保不越界。交叉存储a，b。"""m1 = time.time()for i in range(m):if i%2==0:for j in range(0,n,2):a_dict[matrix[i][j]] = a_dict.get(matrix[i][j],0)+1if j+1< n:b_dict[matrix[i][j+1]] = b_dict.get(matrix[i][j+1],0)+1 else:for j in range(0,n,2):b_dict[matrix[i][j]] = b_dict.get(matrix[i][j],0)+1if j+1 < n:a_dict[matrix[i][j+1]] = a_dict.get(matrix[i][j+1],0)+1m2 = time.time()"""该段为字典排序，此处需要注意是，排序后是一个列表"""a_dict = sorted(a_dict.items(),key=lambda item:item[1],reverse=True)#print(a_dict)b_dict = sorted(b_dict.items(),key=lambda item:item[1],reverse=True)#print(b_dict)"""该段是计算修改次数。思路如上"""m3 = time.time()def compute_result(a_dict,b_dict):result = 0for a in a_dict:for b in b_dict:if a[0]!=b[0]:result = (m*n)-a[1]-b[1]return resultelse:if a[1]>=b[1]:result = b[1]continueelse:result = a[1]breakreturn resultprint(compute_result(b_dict,a_dict))m4 = time.time()print(m2-m1)print(m3-m2)print(m4-m3)
我自己测试的样例保存题目给出的，以及使用numpy随机创建的。由于题目中限定(1≤n,m≤100000,1≤n*m≤100000)，我在创建随机矩阵测试时，使用了shape为(100000,1)和（10000,10）和（1000,100）的矩阵，时间均不超过1秒。
┗|｀O′|┛ 嗷~~！！该刷题了。
