publicintmaxCount(int m, int n, int[][] ops) { if (ops == null || ops.length == 0 || ops[0].length == 0) { return m * n; }
intans=0; int[][] mat = newint[m][n]; for (int[] op : ops) { introw= op[0]; intcol= op[1]; for (inti=0; i < row; i++) { for (intj=0; j < col; j++) { mat[i][j]++; } } }
intmaxVal= mat[0][0]; for (inti=0; i < m; i++) { for (intj=0; j < n; j++) { if (maxVal == mat[i][j]) { ans++; } } }
return ans; }
复杂度分析
时间复杂度:O(km2n2),其中 k 是数组 ops 的长度。
空间复杂度:O(mn),需要创建一个新的二维数组。
方法二: 找到所有操作的交集
思路与算法:
方法一显然会超时,而且因为我们只需要找到最大值的个数,而有满足要求的次数恰好等于操作次数的位置。
我们只需要找到所有操作中的最小值。
代码如下所示:
1 2 3 4 5 6 7 8 9 10
publicintmaxCount(int m, int n, int[][] ops) { intminRow= m; intminCol= n; for (int[] op : ops) { minRow = Math.min(minRow, op[0]); minCol = Math.min(minCol, op[1]); }
return minRow * minCol; }
复杂度分析
时间复杂度:O(k),其中 k 是数组 ops 的长度。
空间复杂度:O(1)。
All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)