leetcode315. Count of Smaller Numbers After Self

elarity 發(fā)布于2019-08-15 15:09 / 2995人閱讀

摘要：當我們希望查詢時，則從根節(jié)點開始尋找其所在的區(qū)間，如果位于左側區(qū)間，則查詢左子樹啊，如果位于右側區(qū)間，則查詢右子樹。如果橫跨了分割點，則分別查詢左子樹的部分和右子樹的部分。

題目要求

You are given an integer array nums and you have to return a new counts array. 
The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0].

輸入一個整數數組nums[i]，返回所有一個新的數組count，該數組第i位上的count[i]表示nums[i]右側小于nums[i]的數字的個數。

簡單說一說Segment Tree

SegmentTree常常用于對于一個數組有多次范圍型查詢的場景。比如計算從L到R之間所有元素的和，或者找到L到R之間的最小元素。這里L和R是會移動的。

SegmentTree本質上是一棵二叉樹，該二叉樹會存儲一個區(qū)間的某種值，如最大值，最小值或是該區(qū)間所有元素的和。如果根節(jié)點代表這個數組A[1...N]，那么它的每一個葉節(jié)點代表一個元素A[i]，每一個非葉節(jié)點代表一個區(qū)間A[i...j]，其中0<=i

當我們希望插入一個SegmentTreeNode時，我們要找到更新所在的區(qū)間，并且遞歸的將其下所有的區(qū)間作出相應的更改。

當我們希望查詢時，則從根節(jié)點開始尋找其所在的區(qū)間，如果位于左側區(qū)間，則查詢左子樹啊，如果位于右側區(qū)間，則查詢右子樹。如果橫跨了分割點，則分別查詢左子樹的部分和右子樹的部分。

思路和代碼

這里我們將從右往左構建一棵二叉搜索樹，這棵樹的每個節(jié)點還將存儲額外的信息，即遍歷到nums[i]時，該節(jié)點的值重復的數量duplicateCount，以及從i到該節(jié)點共有幾個數字小于該節(jié)點而大于其父節(jié)點的值smallerThan（相當于左子樹元素的個數）。

直接從例子入手吧：
假設現(xiàn)在有這樣一個數組[11,6,9,9,3,1,7]
則構造樹的步驟如下：
注：括號中的值分別對用這smallerThan和duplicateCount

插入7
7(0, 1)

此時右側小于7的數字為0個

插入1
   7(1,1)
  /
1(0,1)

當向左插入節(jié)點時，父節(jié)點的smallerThan加一。此時我們看到右側小于1的數字還是0個

插入3
   7(2,1)
  /
1(0,1)
  
   3(0,1)

此時我們看到，3比1大，因此在1處將其作為右節(jié)點插入。此時比3小的數字也就是1和所有比1小的數字，即0+1 = 1這里0對應比1小的數字，1對應數字1的重復次數。

   7(2,1)
  /     
1(0,1)   9(0, 1)
  
   3(0,1)

此時我們在根節(jié)點7處向右插入節(jié)點9，每一次向右插入都意味著有數字比當前的值小，因此比9小的數字的個數為2 + 1 + 0 = 3這里0代表著比7大但是比9小的元素的個數。

插入9
   7(2,1)
  /     
1(0,1)   9(0, 2)
  
   3(0,1)

重復插入9，因此將9的duplicateCount加一，比其小的元素的個數還是為2+1+0=3。

插入6
   7(3,1)
  /     
1(0,1)   9(0, 2)
  
   3(0,1) 
     
      6(0,1)

首先看到根節(jié)點7的smallerThan加一，然后將所有右拐處的節(jié)點值相加，即0+1 + 0+1 + 0 = 2

插入11
   7(3,1)
  /     
1(0,1)   9(0, 2)
          
   3(0,1)   11(0,1)
     
      6(0,1)

那么小于11的數字有幾個呢？沒錯，就是3+1+0+2+0 = 6

代碼實現(xiàn)如下：

    public List countSmaller(int[] nums) {
        LinkedList result = new LinkedList();
        if(nums.length == 0) return result;
        SpecialTreeNode root = new SpecialTreeNode(nums[nums.length-1]);
        result.addFirst(0);
        for(int i = nums.length-2 ; i>=0 ; i--){
            int count = insert(root, nums[i]);
            result.addFirst(count);
        }
        return result;
    }
    
    private int insert(SpecialTreeNode root, int val){
        if(val == root.val){
            root.addDuplicate();
            return root.smallerThan;
        }else if(val < root.val){
            root.addSmallerThan();
            if(root.left==null){
                SpecialTreeNode s = new SpecialTreeNode(val);
                root.left = s;
                return 0;
            }else{
                return insert(root.left, val);
            }
        }else{
            if(root.right == null){
                SpecialTreeNode s = new SpecialTreeNode(val);
                root.right = s;
                return root.smallerThan + root.duplicateCount;
            }else{
                return root.smallerThan + root.duplicateCount + insert(root.right, val);
            }
        }
        
    }
    class SpecialTreeNode{
        int val = 0, smallerThan = 0, duplicateCount = 1;
        SpecialTreeNode left;
        SpecialTreeNode right;
        
        SpecialTreeNode(int val){
            this.val = val;
        }
        
        void addDuplicate(){
            this.duplicateCount++;
        }
        
        void addSmallerThan(){
            this.smallerThan++;
        }
    }

參考文章

Segment Tree Tutorials

想要了解更多開發(fā)技術，面試教程以及互聯(lián)網公司內推，歡迎關注我的微信公眾號！將會不定期的發(fā)放福利哦~

云服務器 GPU云服務器 Smaller Numbers 315cdn Leetcod

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/68894.html

Leetcode[315] Count of Smaller Numbers After Self

摘要：復雜度思路每遍歷到一個數，就把他到已有的中。對于每一個，維護一個和一個自身的數目。比如，然后每次遍歷到一個數，就把對應位置的值加一。比如碰到之后，就變成，然后統(tǒng)計的和。 Leetcode[315] Count of Smaller Numbers After Self ou are given an integer array nums and you have to return a...

dack 2019-08-14 16:41 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self

摘要：我們建立的，其中解決重復值的問題，記錄左子樹的節(jié)點數。給定要找的點，這里的規(guī)律就是，往右下走，說明當前點和當前的的左子樹的值全部比小。我們走到要向右，這是左子樹沒變化，這里也不變。題目細節(jié)描述參看leetcode。今天的重頭戲 LC315 Count of Smaller Numbers After Self.在講這個題目之前，請思考這個問題。在BST找到所有比Node P小的節(jié)點...

Little_XM 2019-08-14 17:20 評論0 收藏0
315. Count of Smaller Numbers After Self

摘要：題目鏈接的題，用來做，這種求有多少的題一般都是。里多加一個信息表示以為的節(jié)點數。也可以做，因為是統(tǒng)計有多少的，其實就是求從最小值到的。的是，要做一個映射，把的值映射到之間。所以先把給一下，用一個來做映射。還有的方法，參考 315. Count of Smaller Numbers After Self 題目鏈接：https://leetcode.com/problems... divi...

cnio 2019-08-14 17:34 評論0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：題目意思就是要一個個的返回當前的最小值。所以解法自然就是。我們需要找出被打亂的點并返回正確結果。然后將兩個不正確的點記錄下來，最后回原來正確的值。如果是葉子節(jié)點，或者只有一個子樹。思想來自于的代碼實現(xiàn)。跳過總結請點這里：https://segmentfault.com/a/11... BST最明顯的特點就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 評論0 收藏0
[LeetCode] 315. Count of Smaller Numbers After Sel

Problem You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i]. Exam...

FingerLiu 2019-08-16 13:53 評論0 收藏0