目录
- leecode 1351. 统计有序矩阵中的负数
- 示例 1
- 提示
- 参考代码
- 定义一颗树
- JAVA Morris
leecode 1351. 统计有序矩阵中的负数
【Java 刷题打卡】
那就干吧! 这个专栏都是刷的题目都是关于二分法的,我会由浅入深、循序渐进,刷题就是这样需要连续不断的记忆--艾宾浩斯记忆法2121112。二分法的内容不多,但是都是每个程序员必备的
给你一个 m * n 的矩阵 grid,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。
请你统计并返回 grid 中 负数 的数目。
示例 1
输入:grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出:8
解释:矩阵中共有 8 个负数。
示例 2:
输入:grid = [[3,2],[1,0]]
输出:0
示例 3:
输入:grid = [[1,-1],[-1,-1]]
输出:3
示例 4:
输入:grid = [[-1]]
输出:1
提示
m == grid.length n == grid[i].length 1 <= m, n <= 100 -100 <= grid[i][j] <= 100
进阶:你可以设计一个时间复杂度为 O(n + m) 的解决方案吗?
Morris 遍历算法整体步骤如下(假设当前遍历到的节点为 x):
如果 x 无左孩子,则访问 x 的右孩子,即 x = x.right。
如果 x 有左孩子,则找到 x 左子树上最右的节点(即左子树中序遍历的最后一个节点,x 在中序遍历中的前驱节点),我们记为 predecessor(前任)。根据predecessor 的右孩子是否为空,进行如下操作。
- 如果predecessor 的右孩子为空,则将其右孩子指向 x,然后访问 x 的左孩子,即 x = x.left。
- 如果 predecessor 的右孩子不为空,则此时其右孩子指向 x,说明我们已经遍历完 x 的左子树,我们将 predecessor 的右孩子置空,然后访问 x 的右孩子,即 x = x.right。
重复上述操作,直至访问完整棵树。
其实整个过程我们就多做一步:将当前节点左子树中最右边的节点指向它,这样在左子树遍历完成后我们通过这个指向走回了 x,且能再通过这个知晓我们已经遍历完成了左子树,而不用再通过栈来维护,省去了栈的空间复杂度。
了解完这个算法以后,其他地方与方法二并无不同,我们同样也是维护一个 pred 变量去比较即可,具体实现可以看下面的代码,这里不再赘述。
参考代码
定义一颗树
class TreeNode { int val; // 头结点 TreeNode left; // 左子树 TreeNode right; // 右子树 TreeNode(int x) { val = x; } } // 测试方法 public static void main(String[] args) { TreeNode treeNode = new TreeNode(1); treeNode.left = new TreeNode(2); treeNode.right = new TreeNode(3); System.out.println("xxxx结果 = " + preorderTraversal(treeNode)); }
JAVA Morris
class Solution { public void recoverTree(TreeNode root) { TreeNode x = null, y = null, pred = null, predecessor = null; while (root != null) { if (root.left != null) { // predecessor 节点就是当前 root 节点向左走一步,然后一直向右走至无法走为止 predecessor = root.left; while (predecessor.right != null && predecessor.right != root) { predecessor = predecessor.right; } // 让 predecessor 的右指针指向 root,继续遍历左子树 if (predecessor.right == null) { predecessor.right = root; root = root.left; } // 说明左子树已经访问完了,我们需要断开链接 else { if (pred != null && root.val < pred.val) { y = root; if (x == null) { x = pred; } } pred = root; predecessor.right = null; root = root.right; } } // 如果没有左孩子,则直接访问右孩子 else { if (pred != null && root.val < pred.val) { y = root; if (x == null) { x = pred; } } pred = root; root = root.right; } } swap(x, y); } public void swap(TreeNode x, TreeNode y) { int tmp = x.val; x.val = y.val; y.val = tmp; } }
以上就是java算法Leecode刷题统计有序矩阵中的负数的详细内容,更多关于java算法统计有序矩阵负数的资料请关注自由互联其它相关文章!