【Leetcode 每日一题】2545. 根据第 K 场考试的分数排序

问题背景

班里有 $m$ 位学生，共计划组织 $n$ 场考试。给你一个下标从 $0$ 开始、大小为 $m\times n$ 的整数矩阵 $score$，其中每一行对应一位学生，而 $score[i][j]$ 表示第 $i$ 位学生在第 $j$ 场考试取得的分数。矩阵 $score$ 包含的整数 互不相同 。
另给你一个整数 $k$。请你按第 $k$ 场考试分数从高到低完成对这些学生（矩阵中的行）的排序。
返回排序后的矩阵。

数据约束

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

解题过程

根据某个标准带着整个数组排序，可以当作模板记下来。
题目保证待排序的元素不重复，那就可以完全不考虑稳定性的问题。
写一下在其它算法中常用 $O(NlogN)$ 量级的简单做法，再把三种常用排序都实现一下当作练习好了。

具体实现

调用 API

class Solution {public int[][] sortTheStudents(int[][] score, int k) {Arrays.sort(score, (o1, o2) -> o2[k] - o1[k]);return score;}
}

归并排序 - 递归版

class Solution {// 二维数组最大长度为 250，开长为 300 的辅助数组就够了private static final int MAX_N = 300;private static final int[][] temp = new int[MAX_N][];private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;mergeSort(score, 0, score.length - 1);return score;}// 归并操作，入参改成二维数组private void merge(int[][] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {// 除了收集元素的标准不一样，其它都可以不变temp[index++] = arr[index1][k] > arr[index2][k] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}// 归并排序，入参改成二维数组private void mergeSort(int[][] arr, int left, int right) {if(left == right) {return;}int mid = left + ((right - left) >>> 1);mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}
}

归并排序 - 非递归版

class Solution {// 二维数组最大长度为 250，开长为 300 的辅助数组就够了private static final int MAX_N = 300;private static final int[][] temp = new int[MAX_N][];private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;mergeSort(score);return score;}// 归并操作，入参改成二维数组private void merge(int[][] arr, int left, int mid, int right) {int index1 = left, index2 = mid + 1, index = left;while(index1 <= mid && index2 <= right) {// 除了收集元素的标准不一样，其它都可以不变temp[index++] = arr[index1][k] > arr[index2][k] ? arr[index1++] : arr[index2++];}while(index1 <= mid) {temp[index++] = arr[index1++];}while(index2 <= right) {temp[index++] = arr[index2++];}System.arraycopy(temp, left, arr, left, right - left + 1);}// 归并排序，入参改成二维数组private void mergeSort(int[][] arr) {int n = arr.length;for(int left, mid, right, step = 1; step < n; step <<= 1) {left = 0;while(left < n) {mid = left + step - 1;if(mid >= n - 1) {break;}right = Math.min(left + (step << 1) - 1, n - 1);merge(arr, left, mid, right);left = right + 1;}}}
}

随机快速排序

class Solution {private static int k;private static int first, last;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;quickSort(score, 0, score.length - 1);return score;}// 交换操作，入参改成二维数组private void swap(int[][] arr, int i, int j) {int[] temp = arr[i];arr[i] = arr[j];arr[j] = temp;}// 划分操作，入参改成二维数组private void partition(int[][] arr, int left, int right, int pivot) {first = left;last = right;int cur = left;while (cur <= last) {if (arr[cur][k] == pivot) {cur++;// 修改区域标准，较大的数往数组左侧交换} else if (arr[cur][k] > pivot) {swap(arr, first++, cur++);} else {swap(arr, cur, last--);}}}// 随机快排，入参改成二维数组private void quickSort(int[][] arr, int left, int right) {if (left >= right) {return;}int pivot = arr[left + (int) (Math.random() * (right - left + 1))][k];partition(arr, left, right, pivot);quickSort(arr, left, first - 1);quickSort(arr, last + 1, right);}
}

堆排序

class Solution {private int k;public int[][] sortTheStudents(int[][] score, int k) {this.k = k;heapSort(score);return score;}// 交换操作，入参改成二维数组private void swap(int[][] arr, int i, int j) {int[] temp = arr[i];arr[i] = arr[j];arr[j] = temp;}private void downAdjust(int[][] arr, int cur, int size) {int child = 2 * cur + 1;while (child < size) {// 修改确定修改目标的条件，用小根堆来完成排序，就能得到从大到小的结果int target = child + 1 < size && arr[child + 1][k] < arr[child][k] ? child + 1 : child;target = arr[target][k] < arr[cur][k] ? target : cur;if (target == cur) {break;}swap(arr, target, cur);cur = target;child = 2 * cur + 1;}}// 建堆操作，入参改成二维数组private void buildHeap(int[][] arr) {int n = arr.length;for (int i = n - 1; i >= 0; i--) {downAdjust(arr, i, n);}}// 堆排序，入参改成二维数组private void heapSort(int[][] arr) {buildHeap(arr);int size = arr.length;while (size > 0) {swap(arr, 0, --size);downAdjust(arr, 0, size);}}
}

总结梳理

Java 中的排序 API 的实现是 Tim Sort，大体上可以理解为在数据量较小的情况下使用 插入排序，通常使用归并排序。这里表现出来的效率不如直接实现的归并排序，猜想是因为整体数据量不是很大，在某些样例上被忽悠使用了效率不是那么高的算法。
归并排序 能够保证时间复杂度在 $O(NlogN)$ 这个量级的同时，算法本身是稳定的，是有必要自己实现排序算法时的首选，只需要考虑开辅助数组会不会影响效率。
快速排序 不仅需要额外的系统栈空间，还不稳定。它有时会成为面试时手撕算法的考题，需要好好掌握。
堆排序 是一种原地算法，但是不稳定，所以通常不是一个好的排序算法的选择。但是堆本身能够维护一系列元素中的最大值或者最小值，是一种非常好用的数据结构。