九章演算法 | Google 2016 面試題6 : Count of Smaller Numbers After Self(數組計數)

01-29

撰文 | JZ

專欄 | 九章演算法

題目描述

給定一個數組nums,返回一個計數數組count，count[i]表示nums中第i個右邊有多少個數小於nums[i]

Example: nums = [5, 2, 6, 1]

輸出[2,1,1,0]

分析解答

此題不難給出O(N^2)的演算法，先窮舉nums中每個位置i，再窮舉右邊的數計算有多少個小於nums[i]。難點在於利用數據結構進行優化從而降低時間複雜度。線段樹（segment tree）和平衡樹（Balanced Binary Tree）是兩種可以使用的數據結構。

線段樹的每個節點表示一段區間，記錄這個區間的某些信息，其基本思想是把區間一分為二，二分為四。。。直到不可再分（因此葉子節點的區間只包含一個數），如此可以把任意區間表示成log（區間大小）個子區間的拼接，以降低查詢時間複雜度。在本題中，假設nums中的數字範圍在0到maxnum之間，那麼建樹的區間為[0,maxnum]（也就是根節點所表示的區間）。

每個節點記錄其表示區間內的數字個數。本題涉及兩種線段樹基本操作：插入和查詢。插入操作把nums[i]插入到線段樹相應位置，同時對所有經過的區間的sum值進行累加；查詢操作需要查詢區間[0,nums[i]-1]所包含的數字個數，利用已經建好的線段樹把查詢區間分割為若干個節點所表示的區間，統計並返回這些節點的sum值之和。

平衡樹用途更廣，代碼複雜度也更高，是一種保持葉子節點深度平衡的二叉搜索樹，有多種方法實現，因篇幅有限不再贅述，大家可以自行在網上搜索學習。