使用BST的多數元素

Question

這個問題已經在鏈接中討論過了。 Find the majority element in array

我知道有更優化的soln比這個，但我不明白下面討論的方法。順便說一句，這是一個未分類的數組。

二叉搜索樹（在此方法中使用）的節點如下。

struct tree 
    { 
    int element; 
    int count; 
    }BST; 

「由一個插入在BST一個元素，並且如果元素是已經存在，則遞增節點的計數。」在任何階段中，如果一個節點的計數變爲大於N/2，則返回。 該方法適用於在數組起始處出現n/2 + 1個多數元素（例如{1,1,1,1,1,2,3,4}）的情況。

如果我們將元素一個接一個地傳遞給一個函數，那麼我們如何比較一個元素是否已經存在並增加計數？

Answer 1

首先結構應該可能有指向子節點的指針。沿線

struct node{ 
int value; 
int count; 
node *leftChild; 
node *rightChild; 
}; 

東西插入在BST你檢查當前的節點是大於還是小於或等於您要插入元素的元素。如果它較小，則向左走，如果它較大，則向右走，如果相等則遞增該節點的計數字段。如果你到達一個空節點（孩子的假期），然後在你所插入的值的位置創建一個新節點，並將計數設置爲1.

最後有兩個變量來跟蹤多數元素以及它發生的次數，並在插入元素時根據需要更新它們。

假設多數元素確實發生n/2或更多次，您不需要額外的變量，但正如您的報價中指出的那樣，只要將節點計數器增加到> = n/2。所以，每當你增加一個計數器，比較n/2。

正如你所指出的，如果任務真的只是在最後知道大多數元素，還有更好的解決方案，但我假設你想堅持BST方法。