网站做图标链接,青岛网站设计选哪家,12333上海公共招聘网官网,微信开发网站建设题目
1901. 寻找峰值 II 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元给你一个 从 0 开始编号 的 m x n 矩阵 mat #xff0c;其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。你可以假设整个矩阵周边…题目
1901. 寻找峰值 II 一个 2D 网格中的 峰值 是指那些 严格大于 其相邻格子(上、下、左、右)的元给你一个 从 0 开始编号 的 m x n 矩阵 mat 其中任意两个相邻格子的值都 不相同 。找出 任意一个 峰值 mat[i][j] 并 返回其位置 [i,j] 。你可以假设整个矩阵周边环绕着一圈值为 -1 的格子。要求必须写出时间复杂度为 O(m log(n)) 或 O(n log(m)) 的算法m mat.lengthn mat[i].length1 m, n 5001 mat[i][j] 10 ^ 5任意两个相邻元素均不相等.
解法
Java 列最大值 二分
第 1 步
类似Leetcode 162. 寻找峰值Java 二分在行内找严格大于左右的元素再找每列的最大值一定是大于上下一定需要找该列的最大值如果这也二分找极大值仅严格大于左右那么可能找到非该列最大值从而导致 左/右 列误判
第 2 步
具体做法 先找中间mid 列找到俩最大值 mat[maxRow][mid] 元素一定严格大于上下的元素如果 mat[maxRow][mid] 严格大于左右的元素则直接返回否则下一步如果 mat[maxRow][mid] mat[maxRow][mid1] 则 maxRow 左边列一定存在否则 maxRow 右边列一定存在 时间复杂度Om*logn空间复杂度O1
代码
/*** Java 列最大值 二分** 第 1 步* 类似162. 寻找峰值 FindPeakElement在行内找严格大于左右的元素再找每列的最大值一定是大于上下* 一定需要找该列的最大值如果这也二分找极大值仅严格大于左右那么可能找到非该列最大值从而导致 左/右 列误判** 第 2 步* 具体做法* * 先找中间mid 列找到俩最大值 mat[maxRow][mid] 元素一定严格大于上下的元素* * 如果 mat[maxRow][mid] 严格大于左右的元素则直接返回否则下一步* * 如果 mat[maxRow][mid] mat[maxRow][mid1] 则 maxRow 左边列一定存在否则 maxRow 右边列一定存在* 时间复杂度Om*logn空间复杂度O1***/public int[] findPeakGrid(int[][] mat) {int leftCol 0;int rightCol mat[0].length - 1;int resCol 0;while (leftCol rightCol) {int midCol ((rightCol - leftCol) 1) leftCol;int maxRow getMaxRow(mat, midCol);if ((midCol 0 || mat[maxRow][midCol] mat[maxRow][midCol - 1]) (midCol mat[0].length - 1 || mat[maxRow][midCol] mat[maxRow][midCol 1])) {resCol midCol;break;}if (midCol mat[0].length - 1 || mat[maxRow][midCol] mat[maxRow][midCol 1]) {rightCol midCol - 1;} else {leftCol midCol 1;}}return new int[]{getMaxRow(mat, resCol), resCol};}private int getMaxRow(int[][] mat, int resCol) {int maxRow 0;for (int i 0; i mat.length; i) {if (mat[maxRow][resCol] mat[i][resCol]) {maxRow i;}}return maxRow;}
