leetcode315. Count of Smaller Numbers After Self

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

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

題目要求

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].

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

簡(jiǎn)單說(shuō)一說(shuō)Segment Tree

SegmentTree常常用于對(duì)于一個(gè)數(shù)組有多次范圍型查詢的場(chǎng)景。比如計(jì)算從L到R之間所有元素的和，或者找到L到R之間的最小元素。這里L(fēng)和R是會(huì)移動(dòng)的。

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

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

當(dāng)我們希望查詢時(shí)，則從根節(jié)點(diǎn)開(kāi)始尋找其所在的區(qū)間，如果位于左側(cè)區(qū)間，則查詢左子樹(shù)啊，如果位于右側(cè)區(qū)間，則查詢右子樹(shù)。如果橫跨了分割點(diǎn)，則分別查詢左子樹(shù)的部分和右子樹(shù)的部分。

思路和代碼

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

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

插入7
7(0, 1)

此時(shí)右側(cè)小于7的數(shù)字為0個(gè)

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

當(dāng)向左插入節(jié)點(diǎn)時(shí)，父節(jié)點(diǎn)的smallerThan加一。此時(shí)我們看到右側(cè)小于1的數(shù)字還是0個(gè)

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

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

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

此時(shí)我們?cè)诟?jié)點(diǎn)7處向右插入節(jié)點(diǎn)9，每一次向右插入都意味著有數(shù)字比當(dāng)前的值小，因此比9小的數(shù)字的個(gè)數(shù)為2 + 1 + 0 = 3這里0代表著比7大但是比9小的元素的個(gè)數(shù)。

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

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

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

首先看到根節(jié)點(diǎn)7的smallerThan加一，然后將所有右拐處的節(jié)點(diǎn)值相加，即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的數(shù)字有幾個(gè)呢？沒(méi)錯(cuò)，就是3+1+0+2+0 = 6

代碼實(shí)現(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

想要了解更多開(kāi)發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

云服務(wù)器 GPU云服務(wù)器 Smaller Numbers 315cdn Leetcod

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/68894.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

elarity

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

iWebFusion：$99/月-Dual E5-2670,128G內(nèi)存,500G SSD硬盤(pán),20

閱讀 600·2021-10-08 10:20
Capoae惡意軟件使用多個(gè)漏洞攻擊Linux系統(tǒng)和Web應(yīng)用程序

閱讀 1490·2021-09-23 11:22
前端實(shí)用小工具

閱讀 3214·2019-08-30 15:55
把鼠標(biāo)、觸摸屏、觸控筆統(tǒng)一起來(lái)，Pointer Events介紹

閱讀 1581·2019-08-28 18:25
CSS 模塊

閱讀 1857·2019-08-28 18:14
eval()不是魔鬼，只是被誤解了（翻譯）

閱讀 1230·2019-08-26 11:37
你可能不知道的前端小技巧

閱讀 2893·2019-08-26 10:18
js事件循環(huán)

閱讀 2420·2019-08-23 18:39

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購(gòu)季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長(zhǎng)期優(yōu)惠，快來(lái)選購(gòu)！

leetcode315. Count of Smaller Numbers After Self

相關(guān)文章