CSDN周赛65期简要题解

最近几期周赛里，貌似 Python 又变成 C 站的亲儿子了。输入形式是列表还不过瘾，现在输出形式也要求是列表，而且是连一个逗号、空格、中括号都不能少的 Python 标准列表形式。虽然对 Python 来说是信手拈来，但总要考虑一下其他编程语言选手的感受吧。纵观这么多在线评测网站，同类型的题目至少会要求譬如“按行输出，每行数字之间空格隔开”这样，而像 C 站这样输入输出的格式这么随意的，还真是独一家。长此以往，越来越多的人也不愿意参与了。

本期非编程题属于我的知识盲区，但正确答案并不难得到，和往常一样，这里就不废话了。

编程题：

第一题数组排序

给你一个整数数组 nums ，请你将数组按照每个值的频率降序排序。如果有多个值的频率相同，请你按照数值本身将它们降序排序。请你返回排序后的数组。

参数限制： 1 <= nums.length <= 100， -100 <= nums[i] <= 100

题目很简单，就是数组的两次排序，内置函数就能完成。但是离大谱的是本题没有用例。随便输入什么，然后点运行都显示 AC，但是却一分没有。我记得以前每次周赛前还会有个测试链接（我就曾因为发现了测试链接而被取消过成绩），难道现在已经没有人测试了吗？

就算是有用例，观察一下示例中的输入输出：

正如文章开头吐槽的那样，输出也要求列表形式 —— 估计能把 C 难受死。

不过一维列表应该还算 OK，中括号和逗号的位置都是固定的，就当组合成字符串输出了。而下一题，却要求二维列表也是以这个格式输出。

第二题求解秩矩阵

给你一个 m x n 的矩阵 matrix ，请你返回一个新的矩阵 answer ，其中 answer[row][col] 是 matrix[row][col] 的秩。这里定义的每个元素的秩是一个整数，表示这个元素相对于其他元素的大小关系，它按照如下规则计算：

秩是从 1 开始的一个整数。
如果两个元素 p 和 q 在同一行或者同一列，那么：如果 p < q ，那么 rank(p) < rank(q) 如果 p == q ，那么 rank(p) == rank(q) 如果 p > q ，那么 rank(p) > rank(q) 秩需要越小越好。

题目保证按照上面规则 answer 数组是唯一的。

参数说明: m == matrix.length n == matrix[i].length 1 <= m n <= 500 -10e9 <= matrix[row][col] <= 10e9

题目给出的三个示例：

而且离谱的是，如果用它提供的“自测”功能，把输入输出放进去，会发现示例中的数组没有空格，而正确答案的输出数组中元素之间却是要求有空格的，也就是 Python 那种列表输出方式。所以，即使千辛万苦做到示例的格式，从而通过了示例，也无法通过本题任何一个实际用例。

而这种输入输出简直就是为 Python 量身定制的，因为压根不需要考虑输出的问题：

matrix = eval(input())
# matrix = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(matrix)

分析

抛开上面这种题目输出格式的问题不谈，其实本题考察的内容和数独很相似。如果把最终输出的结果是一个二维列表，里面每个元素都是相应位置的原数组的“秩”，要求满足条件的这个“秩”尽量要小，一个比较直观的办法，就是不断地从小到大依次去尝试每个数字的“秩”，直到符合条件为止。

拿示例中的 [[20,-21,14],[-19,4,19],[22,-47,24],[-19,4,19]] 为例，直观且暴力的方法就是：

先检查第一个元素 20，然后看同行同列有没有比它小的；
很显然，同行同列都有比它小的，-21 和 -19；
然后分别检查 -21 和 -19 所在的行有没有比他们更小的数字；
-21 所在的列有更小的 -47，但 -19 所在的行和列都没有更小的了，所以 -19 的“秩” 为最小的 1；
继续检查 -47，它所在的行和列都没有更小的了，所以 -47 的“秩”也为最小的 1；
然后再回退一步，检查 -21，除了 -47 之外，同行同列没有比 -21 更小的数字了，所以我们暂时为它赋值“秩”为 2，因为我们不确定，其他地方是否也有 -21，但是却存在 -47 和 -21 之间的数字；
不断重复上述步骤，如果遇到第 6 步提到的冲突情况，则取更大的值，直到所有数字都满足要求。

其实在这个过程中，我们就可以看出，满足要求的“秩”有以下两个特征：