leetcode 315 Count of Smaller Numbers After Self

Little_XM 發(fā)布于2019-08-14 17:20 / 1081人閱讀

摘要：我們建立的，其中解決重復(fù)值的問題，記錄左子樹的節(jié)點(diǎn)數(shù)。給定要找的點(diǎn)，這里的規(guī)律就是，往右下走，說明當(dāng)前點(diǎn)和當(dāng)前的的左子樹的值全部比小。我們走到要向右，這是左子樹沒變化，這里也不變。

題目細(xì)節(jié)描述參看leetcode。

今天的重頭戲 LC315 Count of Smaller Numbers After Self.
在講這個題目之前，請思考這個問題。在BST找到所有比Node P小的節(jié)點(diǎn)個數(shù)。
利用inorder tarvseral我們一直走BST并計(jì)數(shù)，找到p點(diǎn)就返回計(jì)數(shù)得到的值。時間復(fù)雜度worst case O(n).如果我們要找到的是好多節(jié)點(diǎn)的值，如果還用這種方法，時間復(fù)雜度就是O(k*n).
這里我們有大量重復(fù)的工作，每次都從leftmost走，直到找到這個node Pi. 實(shí)際上我們可以預(yù)處理這個BST。把每個節(jié)點(diǎn)小于它的個數(shù)記錄下來。綜合的時間復(fù)雜度就是O(n+klogn).

要快速找到比自己小的數(shù)，就可以建立一個BST來幫助我們。
我們建立的Node(int val, int dup, int leftsum，Node left, Node right) 其中dup解決重復(fù)值的問題，leftsum記錄左子樹的節(jié)點(diǎn)數(shù)。
給一個[3,2,2,6,1]，構(gòu)建出的樹長這樣，其中Node.val(dup, leftsum)表示每個節(jié)點(diǎn)。

建立的細(xì)節(jié)待會兒再講。
假如我們的輸入變?yōu)閇5,3,2,2,6,1]要找比5小的怎么辦？
首先1比5小，total = 1+0. 走到6發(fā)現(xiàn)比5大，去到2，發(fā)現(xiàn)5比2大，total += 2 +0。去到3，發(fā)現(xiàn)5比3大，total += 1+0, 最后total = 4.
假如我們的輸入變?yōu)閇7,3,2,2,6,1]要找比5小的怎么辦？
首先1比7小，total = 1+0. 走到6發(fā)現(xiàn)比7發(fā)，total += 1+3， total = 5。

給定要找的點(diǎn)P，這里的規(guī)律就是，往右下走，說明當(dāng)前點(diǎn)和當(dāng)前的的左子樹的值全部比P.val小。我們計(jì)數(shù)。
往左下走，我們不知道下面節(jié)點(diǎn)是否比p小，需要再重復(fù)上面的判斷。直到找到所有比p小的節(jié)點(diǎn)數(shù)。

給定一個這樣我們自定義的BST，我們直到如何找到。下面就是如何構(gòu)造了。
還是上面那個圖。我們加入5這個點(diǎn)，在走到6的時候，是走到6的左子樹，這是6的左子樹應(yīng)該+1，變成：

這是加入左子樹的情況，現(xiàn)在再繼續(xù)加入7這個點(diǎn)。我們走到6要向右，這是左子樹沒變化，6這里也不變。
和上面的例子稍有不同，我們連續(xù)加入了5，7這兩個點(diǎn)。

        1(1,0)
            
             6(1,4)
            /    
         2(2,0)    7(1,0)
             
              3(1,0)  
                
                 5(1,0)

我們可以試著返回小于7的節(jié)點(diǎn)數(shù)，也就是每次向右走的時候，node上的值求和。total = 1+0 + 1+4 = 6。

代碼如下。

public class Solution {
    class Node {
        Node left, right;
        int val, sum, dup = 1;
        public Node(int v) {
            val = v;
        }
    }
    public List countSmaller(int[] nums) {
        Integer[] ans = new Integer[nums.length];
        Node root = null;
        for (int i = nums.length - 1; i >= 0; i--) {
            root = insert(nums[i], root, ans, i, 0);
        }
        return Arrays.asList(ans);
    }
    private Node insert(int num, Node node, Integer[] ans, int i, int preSum) {
        if (node == null) {
            node = new Node(num);
            ans[i] = preSum;
        } else if (node.val == num) {
            node.dup++;
            ans[i] = preSum + node.sum;
        } else if (node.val > num) {
            node.sum++;
            node.left = insert(num, node.left, ans, i, preSum);
        } else {
            node.right = insert(num, node.right, ans, i, preSum + node.dup + node.sum);
        }
        return node;
    }
}

代碼來源： leetcode mayanist
https://discuss.leetcode.com/...