怎么用java算法統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)

本文小編為大家詳細(xì)介紹“怎么用java算法統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“怎么用java算法統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來(lái)學(xué)習(xí)新知識(shí)吧。

統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)

給你一個(gè) m * n 的矩陣 grid，矩陣中的元素?zé)o論是按行還是按列，都以非遞增順序排列。 

請(qǐng)你統(tǒng)計(jì)并返回 grid 中 負(fù)數(shù) 的數(shù)目。

示例 1

輸入：grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
輸出：8
解釋：矩陣中共有 8 個(gè)負(fù)數(shù)。
示例 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

進(jìn)階：你可以設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為 O(n + m) 的解決方案嗎？

Morris 遍歷算法整體步驟如下（假設(shè)當(dāng)前遍歷到的節(jié)點(diǎn)為 x）：

如果 x 無(wú)左孩子，則訪問(wèn) x 的右孩子，即 x = x.right。

如果 x 有左孩子，則找到 x 左子樹(shù)上最右的節(jié)點(diǎn)（即左子樹(shù)中序遍歷的最后一個(gè)節(jié)點(diǎn)，x 在中序遍歷中的前驅(qū)節(jié)點(diǎn)），我們記為 predecessor（前任）。根據(jù)predecessor 的右孩子是否為空，進(jìn)行如下操作。

• 如果predecessor 的右孩子為空，則將其右孩子指向 x，然后訪問(wèn) x 的左孩子，即 x = x.left。

• 如果 predecessor 的右孩子不為空，則此時(shí)其右孩子指向 x，說(shuō)明我們已經(jīng)遍歷完 x 的左子樹(shù)，我們將 predecessor 的右孩子置空，然后訪問(wèn) x 的右孩子，即 x = x.right。

重復(fù)上述操作，直至訪問(wèn)完整棵樹(shù)。

其實(shí)整個(gè)過(guò)程我們就多做一步：將當(dāng)前節(jié)點(diǎn)左子樹(shù)中最右邊的節(jié)點(diǎn)指向它，這樣在左子樹(shù)遍歷完成后我們通過(guò)這個(gè)指向走回了 x，且能再通過(guò)這個(gè)知曉我們已經(jīng)遍歷完成了左子樹(shù)，而不用再通過(guò)棧來(lái)維護(hù)，省去了棧的空間復(fù)雜度。

了解完這個(gè)算法以后，其他地方與方法二并無(wú)不同，我們同樣也是維護(hù)一個(gè) pred 變量去比較即可，具體實(shí)現(xiàn)可以看下面的代碼，這里不再贅述。

參考代碼

定義一顆樹(shù)

class TreeNode {
    int val;          // 頭結(jié)點(diǎn)
    TreeNode left;    // 左子樹(shù)
    TreeNode right;   // 右子樹(shù)
    TreeNode(int x) {
        val = x;
    }
}
// 測(cè)試方法
 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結(jié)果 = " + 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 節(jié)點(diǎn)就是當(dāng)前 root 節(jié)點(diǎn)向左走一步，然后一直向右走至無(wú)法走為止
                predecessor = root.left;
                while (predecessor.right != null && predecessor.right != root) {
                    predecessor = predecessor.right;
                }
                // 讓 predecessor 的右指針指向 root，繼續(xù)遍歷左子樹(shù)
                if (predecessor.right == null) {
                    predecessor.right = root;
                    root = root.left;
                }
                // 說(shuō)明左子樹(shù)已經(jīng)訪問(wèn)完了，我們需要斷開(kāi)鏈接
                else {
                    if (pred != null && root.val < pred.val) {
                        y = root;
                        if (x == null) {
                            x = pred;
                        }
                    }
                    pred = root;
                    predecessor.right = null;
                    root = root.right;
                }
            }
            // 如果沒(méi)有左孩子，則直接訪問(wèn)右孩子
            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算法統(tǒng)計(jì)有序矩陣中的負(fù)數(shù)”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過(guò)才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。