计数发生（log n）的

鉴于彼此排序整数列表L（在开始时的最低值），不同，返回多少次L [I] = =我为i> = 0。计数发生（log n）的

>>> count_occur([-5,-2,0,3,8]) 
1 
>>> count_occur([-5,-2,2,3,8]) 
2 
>>> count_occur([-5,-2,0,4,8]) 
0

的事情是我应该在最坏情况 O（LOGN）的时间复杂度实现它。

我可以实现O（logn）和平均情况，但显然它不够好。

任何帮助，将不胜感激！

来源

2013-11-22 Splash

请张贴'O（log n）的'一般的情况下的解决方案。 –

[dificulty解决O（logn）中的代码的可能的重复]（http://stackoverflow.com/questions/20148557/dificulty-solving-a-code-in-ologn） –

L[i] == i只能对i的连续范围的值为真。（你能明白为什么吗？）因此，我们可以通过二进制搜索最左边和最右边的值来解决O（log（n））最差情况下的这个问题，其中L[i] - i == 0。

使用的二进制搜索的bisect模块：

import bisect 

class HelperList(object): 
    """Lazily computes l[i] - i to determine values.""" 
    def __init__(self, l): 
     super(HelperList, self).__init__() 
     self.l = l 
    def __len__(self): 
     return len(self.l) 
    def __getitem__(self, i): 
     return self.l[i] - i 

def count_occur(l): 
    helperlist = HelperList(l) 
    leftmost = bisect.bisect_left(helperlist, 0) 
    if l[leftmost] != leftmost: 
     return 0 
    return bisect.bisect_right(helperlist, 0) - leftmost

来源

2013-11-22 20:48:11 user2357112

计数发生（log n）的

回答

相关问题