手机网站微信咨询,网站首页psd格式怎么做,成都极客联盟,小程序源码是什么创建二维前缀和数组
两个for循环#xff0c;外循环表示子矩阵的左上角#xff08;x1,y1#xff09;#xff0c;内循环表示子矩阵的右下角#xff08;x2,y2#xff09;
两个for循环遍历#xff0c;计算子矩阵的元素总和
四个变量#xff0c;暴力破解的时间复杂度为O(…创建二维前缀和数组
两个for循环外循环表示子矩阵的左上角x1,y1内循环表示子矩阵的右下角x2,y2
两个for循环遍历计算子矩阵的元素总和
四个变量暴力破解的时间复杂度为O(m^2*n^2)m、n为matrix数组的行数和列数 优化
计算每一行的前缀和而不是整个矩阵的前缀和。
取不同的两个列(j1,j2)计算以这两个列为边界计算每一行的前缀和这就是二维前缀和
这样就可以减少一个变量遍历时间复杂度为O(m^2*n)m、n为matrix数组的行数和列数 代码
import org.junit.Test;import java.util.HashMap;
import java.util.Map;public class SubmatrixNumber {Testpublic void test() {int[][] matrix new int[][]{{0, 1, 0}, {1, 1, 1}, {0, 1, 0}};
// for (int[] arr:getPrefixAnd(matrix)) {
// for (int i:arr) {
// System.out.print(i );
// }
// System.out.println();
// }System.out.println(submatrixNumber(matrix, 0));//4int[][] matrix1 new int[][]{{1, -1}, {-1, 1}};System.out.println(submatrixNumber(matrix1, 0));//5int[][] matrix2 new int[][]{{904}};System.out.println(submatrixNumber(matrix2, 0));//0}public static int submatrixNumber(int[][] matrix, int target) {int[][] sum getPrefixAnd1(matrix);int ans 0;MapInteger, Integer count new HashMap();//负责记录计算出的每两列之间的前缀和出现的次数int endY 1;while (endY matrix[0].length) {for (int startY 0; startY endY; startY) {//两个列的边界int prefixAnd 0;count.clear();//两个列的边界不同此时计算出的前缀和不同负责记录的map集合需要初始化count.put(0, 1);//当矩阵为空时需要记录0出现了1次for (int k 1; k matrix.length; k) {//遍历行prefixAnd (sum[k][endY] - sum[k][startY]);//计算以这两个列为边界计算每一行的前缀和if (count.containsKey(prefixAnd - target)) {//count集合中是否存在key值为temp-target的数即为temp-target这个数是否是第一次出现ans count.get(prefixAnd - target);//不是第一次则取value值加上}count.put(prefixAnd, count.getOrDefault(prefixAnd, 0) 1);//记录次数加一//defaultValue - 当指定的key并不存在映射关系中则返回的该默认值//即如果是第一次出现则默认的次数记为0}}endY;}return ans;}public static int[][] getPrefixAnd(int[][] matrix) {int[][] sum new int[matrix.length][matrix[0].length];for (int i 0; i matrix.length; i) {for (int j 0; j matrix[0].length; j) {if (i 0 j 0) {//第一行sum[i][j] sum[i][j - 1] matrix[i][j];} else if (j 0 i 0) {sum[i][j] sum[i - 1][j] matrix[i][j];} else if (i 0 j 0) {sum[0][0] matrix[0][0];} else {sum[i][j] sum[i - 1][j] sum[i][j - 1] - sum[i - 1][j - 1] matrix[i][j];}}}return sum;}//sum[0][0] 0public static int[][] getPrefixAnd1(int[][] matrix) {int[][] sum new int[matrix.length1][matrix[0].length1];for (int i 1; i matrix.length; i) {for (int j 1; j matrix[0].length; j) {sum[i][j] sum[i][j - 1] matrix[i - 1][j - 1];}}return sum;}
}
