計算左邊的數組中的數字並且比元素大

Question

我需要幫助解決這個問題，我給出了N個元素的數組，並且我想要生成一個新的數組，其中每個索引我都會保留多少個數字位於此索引的左側，並且大於此元素。

假設我們有這個數組{3,2,1,0}，並且我想要生成這個數組{0,1,2}。在第二陣，我們是零，因爲有上左部件3的任何元素，我們有1，因爲3號是2號的左邊，這是更大的...

我想這可能是與完成二叉樹索引樹，但我不知道如何實現它。

在此先感謝。即每個節點的右子樹的當前大小 -

Answer 1

您可以通過構建一個二叉樹和保存沿途節點上的一些元數據在NlogN做到這一點。在添加每個元素之後，您可以計算以前添加到樹的元素的數量。我會假設你知道如何通過逐個插入節點來創建二叉搜索樹。因此，讓我們這個分裂爲東西兩部，我們需要做的：

維護每個節點的右子樹的大小：在每個節點上，我們挑選如果電流值居右子樹（當前值都比較大節點值）或左子樹。如果我們選擇正確的話，將右邊的子樹大小的值加1。

計算之前插入的元素數量大於當前元素：假設對於每個節點我們知道右側子樹的大小，現在我們可以計算當前元素左側有多少元素是大於它（即左側的元素已經添加到樹中）。再次，我們遵循二叉樹插入操作。在每個節點上，如果當前值小於節點，則意味着該節點及其整個右側子樹都大於當前值。所以對於我們遍歷的每個節點，我們保留所有大於當前值的元素的總和。當我們完成插入樹時，我們有我們正在尋找的總和。

讓我知道你是否需要任何澄清。