根据第 K 场考试的分数排序

标签: 数组 矩阵 排序

难度: Medium

班里有 m 位学生，共计划组织 n 场考试。给你一个下标从 0 开始、大小为 m x n 的整数矩阵 score ，其中每一行对应一位学生，而 score[i][j] 表示第 i 位学生在第 j 场考试取得的分数。矩阵 score 包含的整数 互不相同 。

另给你一个整数 k 。请你按第 k 场考试分数从高到低完成对这些学生（矩阵中的行）的排序。

返回排序后的矩阵。

示例 1：

输入：score = [[10,6,9,1],[7,5,11,2],[4,8,3,15]], k = 2
输出：[[7,5,11,2],[10,6,9,1],[4,8,3,15]]
解释：在上图中，S 表示学生，E 表示考试。
- 下标为 1 的学生在第 2 场考试取得的分数为 11 ，这是考试的最高分，所以 TA 需要排在第一。
- 下标为 0 的学生在第 2 场考试取得的分数为 9 ，这是考试的第二高分，所以 TA 需要排在第二。
- 下标为 2 的学生在第 2 场考试取得的分数为 3 ，这是考试的最低分，所以 TA 需要排在第三。

示例 2：

输入：score = [[3,4],[5,6]], k = 0
输出：[[5,6],[3,4]]
解释：在上图中，S 表示学生，E 表示考试。
- 下标为 1 的学生在第 0 场考试取得的分数为 5 ，这是考试的最高分，所以 TA 需要排在第一。
- 下标为 0 的学生在第 0 场考试取得的分数为 3 ，这是考试的最低分，所以 TA 需要排在第二。

提示：

  • m == score.length
  • n == score[i].length
  • 1 <= m, n <= 250
  • 1 <= score[i][j] <= 105
  • score 由 不同 的整数组成
  • 0 <= k < n

Submission

运行时间: 27 ms

内存: 21.3 MB

class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        score.sort(key=lambda s:-s[k])
        return score

Explain

题解使用了Python内置的sort函数来根据第k场考试的分数对学生进行排序。通过传递一个lambda函数给sort的key参数，该lambda函数返回每个学生第k场考试的分数的负值（-s[k]），这使得sort函数按照第k场考试的分数从高到低进行排序。由于所有数字都是不同的，排序后返回更新的score列表。

时间复杂度: O(m log m)

空间复杂度: O(m)

class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        # 使用内置的sort方法，通过lambda表达式提供自定义的排序键
        # lambda表达式 -s[k] 使得学生可以根据第k场考试的分数降序排序
        score.sort(key=lambda s: -s[k])
        # 返回排序后的成绩矩阵
        return score

Explore

在Python中，默认的排序顺序是升序。使用`-s[k]`作为排序键是为了将排序顺序改为降序，即从高分到低分。如果直接使用`s[k]`进行排序，则结果会是从低分到高分，这通常不是考试成绩排序的预期顺序。通过使用负值，我们可以避免使用额外的参数如`reverse=True`，这可以使代码更简洁。

Timsort算法是Python内置排序函数的基础，它是一种混合排序算法，结合了归并排序和插入排序的优点。Timsort适用于多种数据类型和数据分布，特别是在处理部分有序的数据时非常高效。与快速排序不同，Timsort在最坏情况下仍能保持O(n log n)的时间复杂度，而快速排序在最坏情况下可能退化到O(n^2)。与堆排序相比，Timsort通常在实际应用中更快，因为它更好地利用了数据的局部顺序性。

在这个问题中，假设`m`是学生数量，而`n`是每个学生的考试数量。由于排序操作只涉及到学生间的比较，即只排序`m`个元素，因此`n`的大小直接影响不大。然而，`n`的值可能间接影响性能，因为每次比较都需要访问学生的第`k`次考试的成绩，如果`n`很大，那么访问这些成绩可能会有轻微的性能开销，尤其是在内存访问模式不是非常高效的情况下。

如果矩阵`score`中存在重复的分数，现有的排序策略仍然有效。Python的排序是稳定的，这意味着具有相同键值（即相同的分数）的元素将保留它们原始的相对顺序。题解中提到的互不相同的整数意味着每次比较都有一个确定的大小关系（不会有相等的情况），这简化了排序逻辑，但实际上即使有重复分数，排序逻辑也不会受到影响。