计数出现

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）