計數出現

Question

假設我已經整理排列，我想算元素X的出現

僞代碼：

SET Lo to 1 
SET Hi to array length 
WHILE Lo <= Hi 
    SET Mid to (Lo + Hi)/2 
    IF X < array[Mid] THEN 
    SET Hi to Mid - 1 
    ELSE IF X > array[Mid] THEN 
    SET Lo to Mid + 1 
    ELSE 
    RETURN Mid 
    ENDIF 
ENDWHILE 
RETURN -1 

現在假設我想找到的所有出現數組中的所有數字，但我沒有成功。

例如 - A = [1,1,2,2,2,2,5,5,5]返回（1,2），（2,4），（5,3）

算法必須是O（log（n））
有幫助嗎？

Answer 1

除非數組是非常大的，並且只包含幾個不同的電話號碼，只是做一個線性掃描整個數組。每當您檢測到更改時，輸出計數並重置計數器。

對於這個問題作爲當前的陳述O（日誌（n））的算法是不可能的，因爲結果的輸出在最壞的情況已經花費爲O（n）不管一個人如何到達它。

Answer 2

我會做這樣的事情：

int nrOfX = 0; 
int SortedArray[N]; 
Lo = 0; 
Hi = N-1; 
Mid = N-1 div 2; 
while (((sortedArray[Lo] < x) or (sortedArray[Hi] > x)) and (Lo != Hi)) { 
    if (sortedArray[Mid] < x) { 
     Lo = Mid; 
    } else if (sortedArray[Mid] > x) { 
     Hi = Mid; 
    } else if (sortedArray[Mid] == x) { 
     Hi = Mid; 
     Lo = Mid; 
    } 
    Mid = (Lo + Hi) div 2; 
} 
while (sortedArray [Lo - 1] == x) { 
    Lo--; 
} 
while (sortedArray [Hi + 1] == x) { 
    Hi++; 
} 
if (sortedArray[Lo] == x) { 
    return ((Hi - Lo) + 1); 
} else { 
    return 0; 
} 

沒有測試過，所以你可能不得不調整它一點得到它的工作，但總的想法是，你首先得羅嗨斧頭價值，並從那裏擴大他們在陣列上的不同方向。如果x完全不顯示，則最終得到Lo == Hi，並且由於sortedArray [Lo] == 0，因此此函數將返回0.如果數組中包含#x，則它應該在O（log N）左右運行低。 然而，這隻對找到1個特定數字的出現次數非常有用，即x。如果你想知道所有的數字，你會得到O（N）在最壞的情況下，因爲你必須檢查每個數字，當他們都不同。

Answer 3

您可以O（LOGN）爲此在最好的情況下和O（N * LOGN）最壞的情況如下： -

1. 尋找下一個更大數量的指數（nextind ）使用修改的二進制搜索。
2. 存儲電流，nextind-currentind
3. currentind = nextind和電流= ARR [nextind]
4. 做1至3，直到到達數組的末尾

時間複雜度：

O（M * logn）時間，其中m是在陣列的獨特編號的計數。如果m是 可忽略不計比O（logn）