设计衣服的网站,深圳网博网站建设,网站站群建设进度,网络营销有什么方式问题背景
班里有 m m m 位学生#xff0c;共计划组织 n n n 场考试。给你一个下标从 0 0 0 开始、大小为 m n m \times n mn 的整数矩阵 s c o r e score score#xff0c;其中每一行对应一位学生#xff0c;而 s c o r e [ i ] [ j ] score[i][j] score[i][j] 表示…问题背景
班里有 m m m 位学生共计划组织 n n n 场考试。给你一个下标从 0 0 0 开始、大小为 m × n m \times n m×n 的整数矩阵 s c o r e score score其中每一行对应一位学生而 s c o r e [ i ] [ j ] score[i][j] score[i][j] 表示第 i i i 位学生在第 j j j 场考试取得的分数。矩阵 s c o r e score score 包含的整数 互不相同 。 另给你一个整数 k k k。请你按第 k k k 场考试分数从高到低完成对这些学生矩阵中的行的排序。 返回排序后的矩阵。
数据约束 m s c o r e . l e n g t h m score.length mscore.length n s c o r e [ i ] . l e n g t h n score[i].length nscore[i].length 1 ≤ m , n ≤ 250 1 \le m, n \le 250 1≤m,n≤250 1 ≤ s c o r e [ i ] [ j ] ≤ 105 1 \le score[i][j] \le 105 1≤score[i][j]≤105 s c o r e score score 由 不同 的整数组成 0 ≤ k n 0 \le k \lt n 0≤kn
解题过程
根据某个标准带着整个数组排序可以当作模板记下来。 题目保证待排序的元素不重复那就可以完全不考虑稳定性的问题。 写一下在其它算法中常用 O ( N l o g N ) O(NlogN) 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 ( N l o g N ) O(NlogN) O(NlogN) 这个量级的同时算法本身是稳定的是有必要自己实现排序算法时的首选只需要考虑开辅助数组会不会影响效率。 快速排序 不仅需要额外的系统栈空间还不稳定。它有时会成为面试时手撕算法的考题需要好好掌握。 堆排序 是一种原地算法但是不稳定所以通常不是一个好的排序算法的选择。但是堆本身能够维护一系列元素中的最大值或者最小值是一种非常好用的数据结构。
