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

题目链接：3567. 子矩阵的最小绝对差（中等）

算法原理：

解法：暴力枚举

45ms击败9.09%

时间复杂度O((m-k+1)(n-k+1) · k² · log k)，排序操作是复杂度的主导项

思路很简单

①在能够构成k×k子矩阵的前提下枚举每个左上角(i,j)

②针对每个左上角，将其所在k×k矩形的每个元素都扔进Set里天然去重

③将去重后的元素再扔进顺序表排序，因为只有排序后的两两数之间才能产生最小值

④更新两数间最小绝对值，将结果赋给结果数组ret[i][j]

优化

12ms击败90.91%

时间复杂度O((m-k+1)(n-k+1) · k² · log k)，排序操作是复杂度的主导项

我们也可以用一个数组来替代上述的Set和顺序表操作

将数扔进数组中，对数组排序，由于数组升序，因此我们仅需保证两两的数不同再相减即可

Java代码：

class Solution { public int[][] minAbsDiff(int[][] grid, int k) { int m=grid.length,n=grid[0].length; int[][] ret=new int[m-k+1][n-k+1]; for(int i=0;i<m-k+1;i++){ for(int j=0;j<n-k+1;j++){ Set<Integer> hash=new HashSet<>(); for(int a=0;a<k;a++){ for(int b=0;b<k;b++){ hash.add(grid[i+a][j+b]); } } List<Integer> list=new ArrayList<>(); for(int x:hash) list.add(x); Collections.sort(list); int mn=0x3f3f3f3f; for(int l=0;l<list.size()-1;l++) mn=Math.min(mn,Math.abs(list.get(l)-list.get(l+1))); ret[i][j]=mn==0x3f3f3f3f?0:mn; } } return ret; } }

class Solution { //优化 public int[][] minAbsDiff(int[][] grid, int k) { int m=grid.length,n=grid[0].length; int[][] ret=new int[m-k+1][n-k+1]; int[] t=new int[k*k]; for(int i=0;i<m-k+1;i++){ for(int j=0;j<n-k+1;j++){ int index=0; for(int a=0;a<k;a++){ for(int b=0;b<k;b++){ t[index++]=grid[i+a][j+b]; } } Arrays.sort(t); int mn=0x3f3f3f3f; for(int l=0;l<k*k-1;l++) if(t[l]<t[l+1]) mn=Math.min(mn,t[l+1]-t[l]); ret[i][j]=mn==0x3f3f3f3f?0:mn; } } return ret; } }