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 分，是最高分，所以排在第一位。
- 下标为 0 的学生在考试 2 中得了 9 分，是第二高分，所以排在第二位。
- 下标为 2 的学生在考试 2 中得了 3 分，是最低分，所以排在第三位。

示例 2：

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

约束条件：

  • m == score.length
  • n == score[i].length
  • 1 <= m, n <= 250
  • 1 <= score[i][j] <= 10^5
  • score 包含互不相同的整数
  • 0 <= k < n

解题思路

这道题要求按照第 k 场考试的分数对学生进行排序，是一个典型的按特定列排序的问题。

解题思路：

  1. 直接排序法（推荐）：利用自定义比较器，直接对整个二维数组进行排序。比较函数以第 k 列的值为准，从高到低排序。这是最直观和简洁的方法。

  2. 选择排序法：根据题目提示，可以实现选择排序的思想。每次找到剩余行中第 k 列值最大的行，将其交换到当前位置。虽然这种方法时间复杂度较高，但体现了排序的基本思想。

  3. 索引排序法：先创建索引数组，对索引按第 k 列的值进行排序，然后根据排序后的索引重新构建结果矩阵。

直接排序法是最优解，利用内置的高效排序算法，代码简洁且性能好。在实际编程中，应该优先选择这种方法，除非有特殊要求需要手动实现排序算法。

关键点是正确设置比较器：对于从高到低排序，当比较两行时，返回 row1[k] > row2[k] 的结果。

代码实现

class Solution {
public:
    vector<vector<int>> sortTheStudents(vector<vector<int>>& score, int k) {
        sort(score.begin(), score.end(), [k](const vector<int>& a, const vector<int>& b) {
            return a[k] > b[k];
        });
        return score;
    }
};

class Solution:
    def sortTheStudents(self, score: List[List[int]], k: int) -> List[List[int]]:
        return sorted(score, key=lambda x: x[k], reverse=True)

public class Solution {
    public int[][] SortTheStudents(int[][] score, int k) {
        Array.Sort(score, (a, b) => b[k].CompareTo(a[k]));
        return score;
    }
}

var sortTheStudents = function(score, k) {
    return score.sort((a, b) => b[k] - a[k]);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(m log m)，其中 m 是学生数量，主要是排序的时间复杂度
空间复杂度O(1)，只使用了常数额外空间（不考虑排序算法内部使用的栈空间）

相关题目