java算法Leecode刷題統計有序矩陣中的負數

Posted on by

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算法統計有序矩陣負數的資料請關註WalkonNet其它相關文章！

推薦閱讀：