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

问题背景

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

数据约束

$m = score . l e n g t h$
$n = score [i] . l e n g t h$
$\le m, n \le 250$
$\le score[i][j] \le 105$
$score$ 由不同的整数组成
$\le k \lt n$

解题过程

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

具体实现

调用 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 (Nl o g N)$ 这个量级的同时，算法本身是稳定的，是有必要自己实现排序算法时的首选，只需要考虑开辅助数组会不会影响效率。
快速排序不仅需要额外的系统栈空间，还不稳定。它有时会成为面试时手撕算法的考题，需要好好掌握。
堆排序是一种原地算法，但是不稳定，所以通常不是一个好的排序算法的选择。但是堆本身能够维护一系列元素中的最大值或者最小值，是一种非常好用的数据结构。