美团4.16笔试前四题代码复盘（第五题没做）
首先吐槽一下题量。。都是五道代码，网易互娱给两个半小时美团只给两个小时（不过美团的似乎是简单一点）
第一题：
n个学生，m个科目，现在学校要给优秀学生颁奖，评判标准是至少在一个科目上获得了最高分（就是>=其他所有同学的成绩）
实不相瞒，这题我卡了30min。。。因为我最开始看错题了，这是一个n*m数组，每一行是一个学生的各科分数，每一列是各科的各个学生的分数（不懂你们听不听得懂），反正就是，如果你要比较你是不是该科目最高分，你应该去和你那一整列的数据比大小，而不是拿行比大小。换言之，就是普通遍历二维数组不是先行后列吗，这题就是先列后行遍历
结果我最开始先是看错题，然后又在遍历的时候混乱得不行，浪费了好多好多时间。。
直接上代码吧，看代码你们就懂了
def max(list,i,j): res=0 for z in range(i): if res<=list[z][j]: res=list[z][j] return res n,m=map(int,input().split())#n个学生 m个考试科目 list=[] for i in range(n): list.append([int (i) for i in input().split()]) res=[] for i in range(m): max_grade=max(list,n,i) for j in range(n): if list[j][i]>=max_grade and j not in res: res.append(j) print(len(res))
第二题：
第一题我做完心就凉了半截了，这一共五道题两小时，第一题我就花了半多个小时，我没了
但是没想到第二题，两分钟就能写完。。
题目是给定四个数a,b,m,x 然后有个运算法则是x=(a*x+b)%m，因为是取余，所以x是重复的，现在叫你把重复部分的长度打印出来（比如说是1,2,3,4,1,2,3,4....这样循环，你就输出4就行）
公式都给你了你就套着算不就行了。。。这题的意义在哪啊
a,b,m,x=map(int,input().split()) list=[] while True: x=(a*x+b)%m if x not in list: list.append(x) else : break print(len(list))第四题：
先说第四题，因为我AC了
第四题上来先给了一个“类中位数”的概念，反正就和中位数的概念差不多，但是这个类中位数一定要在非递减数组里面，并且是取地板计算（看我代码都懂什么意思了），然后现在给定一个数组和一个key，问在数组中最少添加几个数之后，这个key能成为数组的类中位数
比如说，现在给定一个数组2,3,3,3 key是2 那么你就最少需要添加两个数1,1在最前面 。因为你添加一个1后，数组变成1,2,3,3,3，中位数还是3.当你再添加一个1变成1,1,2,3,3,3后，中位数就成了2
看到这里是不是就有思路了，这不就是一个二分查找吗。和“从一个先增后减的数组中找到那个拐点”的思路一模一样啊，你二分之后的中位数要是大于key，那就在最左边添数呗，小于key就在最右边添数呗。因为这是中位数，只用保证位置相同，因为每次添数就添最大值和最小值就行（题目给了是1到1000000）
（我这个代码或许有点问题，因为当时存的时候存岔了，我交上去的代码是AC的）
def middle(list): n=len(list) temp=(n+1)//2 return list[temp-1] n,k=map(int,input().split()) list=[int (i) for i in input().split()] res=0 if k not in list: list.append(k) res+=1 list.sort() temp=middle(list) while True: if temp>k and list[0]>=1: list.insert(0,1) res+=1 if temp<k and list[-1]<=100000: list.append(100000) res+=1 temp=middle(list) if temp ==k: break print(res)第三题：
第三题我做出来了但是要不就是超时一点点要不就是爆内存一点点（真的就一点点，Python要求3000ms之内，我的代码3004.。。怎么优化都优化不了）
这题给了一个数学概念，大概就是对于两个点（x,y），他们有一个排列组合(x,x),(x,y),(y,x),(x,x)，注意是可以重复的。那么对于n个点来说，两两之间都可以排列，就可以排列出n^2个组合。现在对着n^2的组合进行排序，排序规则就是和字典序一样。现在叫你返回排序后第k个组合的值
比如说(1,2)就有排序(1,1),(1,2)、(2,1)、(2,2)。如果此时k=3，就输出（2,1）
首先！！！
这题不是全排列！！
全排列是不和自己排的！！反正我一开始用Python的permutations，然后就卡了二十分钟在这。。。一直没发现这个问题。其实这题就是两次遍历数组就完事了，根本不是什么鬼全排列
然后我的思路就是自己定义一下比大小，自己写个排序（我写的快排），然后最后输出。然而这样过不去我真的不知道为什么。。。有可能是Python自己的原因，因为真的有些题目是用Python怎么写的超时的。我真的想不出什么别的好方法了，难道说还可以用动规写？？不可能啊
先贴一下代码，然后我再一个个解释一下
import itertools def __sub__(self,rhs): if self[0]>rhs[0]: return 1 elif self[0]<rhs[0]: return -1 elif self[0]==rhs[0]: if self[1]>rhs[1]: return 1 if self[1]<rhs[1]: return -1 if self[1]==rhs[1]: return 0 def quick_sort(list,left,right): #list:[()] if left>=right: return start=left end=right pivol =list[start] while start<end: while start<end and __sub__(list[end],pivol)>=0: end-=1 list[start]=list[end] while start <end and __sub__(list[start],pivol)<=0: start+=1 list[end]=list[start] list[start]=pivol quick_sort(list,left,start-1) quick_sort(list,start+1,right) def permute(x,y,res): list=[x,y] temp=itertools.permutations(list) #res=[] for i in temp: res.append(i) return res n,k=map(int,input().split()) list=[int (i) for i in input().split()] #list.sort() res=[] for i in range(len(list)): for j in range(len(list)): res.append((list[i],list[j])) #res.append((list[j],list[i])) quick_sort(res,0,len(res)-1) print(res[k-1])首先，permute就是那个全排列函数！！！千万不要用，用了就上当了，你只需要两次从头到尾的遍历依次加进list里面就行
Python里面（a,b）代表一个元组，元组就是一个不能修改元素的list，但是依旧可以用下标访问元组里面的数据，这里用元组存储单纯是因为输出方便
__sub__就是我自定义的减法（这好像是运算符重载但是我不会用hhhh）,self和rhs就是两个组合(前文说的用元祖储存的东西)，比较大小用字典序，第一个大就大，第一个小就小，第一个相等就比第二个
quick_sort就是我自己写的排序，这里用的快排，list的形式我在注释里写了 是[()]形式，所有的组合构成一个list，而各个组合用()存储（也就是前文说的元祖）
因为之前有同学反馈Python代码看不懂。。我其实学过C++和JAVA但是我都忘得差不多了，我就尽可能地用大白话描述一下我的思路
第五题：
没时间做了。。瞟了一眼题感觉好复杂啊。。求个大佬来贴一下AC代码我再去研究一会
