A.每日一题：3567. 子矩阵的最小绝对差

题目链接3567. 子矩阵的最小绝对差中等算法原理解法暴力枚举45ms击败9.09%时间复杂度O((m-k1)(n-k1) · k² · log k)排序操作是复杂度的主导项思路很简单①在能够构成k×k子矩阵的前提下枚举每个左上角(i,j)②针对每个左上角将其所在k×k矩形的每个元素都扔进Set里天然去重③将去重后的元素再扔进顺序表排序因为只有排序后的两两数之间才能产生最小值④更新两数间最小绝对值将结果赋给结果数组ret[i][j]优化12ms击败90.91%时间复杂度O((m-k1)(n-k1) · k² · log k)排序操作是复杂度的主导项我们也可以用一个数组来替代上述的Set和顺序表操作将数扔进数组中对数组排序由于数组升序因此我们仅需保证两两的数不同再相减即可Java代码class Solution { public int[][] minAbsDiff(int[][] grid, int k) { int mgrid.length,ngrid[0].length; int[][] retnew int[m-k1][n-k1]; for(int i0;im-k1;i){ for(int j0;jn-k1;j){ SetInteger hashnew HashSet(); for(int a0;ak;a){ for(int b0;bk;b){ hash.add(grid[ia][jb]); } } ListInteger listnew ArrayList(); for(int x:hash) list.add(x); Collections.sort(list); int mn0x3f3f3f3f; for(int l0;llist.size()-1;l) mnMath.min(mn,Math.abs(list.get(l)-list.get(l1))); ret[i][j]mn0x3f3f3f3f?0:mn; } } return ret; } }class Solution { //优化 public int[][] minAbsDiff(int[][] grid, int k) { int mgrid.length,ngrid[0].length; int[][] retnew int[m-k1][n-k1]; int[] tnew int[k*k]; for(int i0;im-k1;i){ for(int j0;jn-k1;j){ int index0; for(int a0;ak;a){ for(int b0;bk;b){ t[index]grid[ia][jb]; } } Arrays.sort(t); int mn0x3f3f3f3f; for(int l0;lk*k-1;l) if(t[l]t[l1]) mnMath.min(mn,t[l1]-t[l]); ret[i][j]mn0x3f3f3f3f?0:mn; } } return ret; } }