如何计算给定项在（已排序）列表中的出现次数？

Question

我被要求创建一个方法，能够返回一个列表中某个特定项出现的次数。我知道怎么写代码来查找特定的项，但我该怎么写代码来计算一个随机项出现的次数呢？

比如说，如果我有一个 list [4, 6, 4, 3, 6, 4, 9]，当我输入 s1.count(4) 时，它应该返回 3，而 s1.count(6) 应该返回 2。

不过，我不能使用任何内置的函数。

在最近的一次作业中，我被要求计算字符串中 sub string "ou" 出现的次数，我是这样写的：

if len(astr) < 2:
    return 0
else:
    return (astr[:2] == "ou")+ count_pattern(astr[1:])

这样写可以吗？

def count(self, item):
    num=0
    for i in self.s_list:
        if i in self.s_list:
            num[i] +=1
def __str__(self):
    return str(self.s_list)

Answer 1

其实，从大O表示法来看，最有效的方法是O(log n)。@pst的方法会得到O(log n + s)，如果数组里的元素都是相同的，这个结果可能会变成线性的。

要实现O(log n)，可以使用两次二分查找（虽然这样是O(2log n)，但我们忽略常数，所以还是算O(log n)）。这两次查找需要稍微改动一下，不进行相等的判断，这样所有的查找都会失败。不过，当查找失败（也就是低位大于高位）时，我们就返回低位的值。

在第一次查找中，如果中间的值大于你要找的值，就继续查找数组的高位部分；否则，就查找低位部分。在第二次查找中，比较的方向要反过来。

第一次查找会找到相等元素的右边界，第二次查找会找到左边界。最后，只需相减就能得到元素出现的次数。这个算法是根据Skiena的描述来的。

Answer 2

如果我让你数一下下面这个列表里有多少个数字4，你会怎么做呢？

1 4 2 4 3 8 2 1 4 2 4 9 7 4

你可以先记住“还没有4”，然后每当遇到一个等于4的元素，就加1。要遍历一个列表，你可以使用一个叫做for语句的东西。假设列表中的一个元素叫做el，你可以这样检查它是不是4：

if el == 4:
  # TODO: Add 1 to the counter here

---

关于你修改的内容：

你现在在测试if i in self.s_list:，这没有什么意义，因为i是列表中的一个元素，所以它总是会在里面。

当你想给一个数字加1时，只需要写num += 1。只有在你想访问列表或字典的值时，才需要用括号。

另外，别忘了在函数的最后加上return num，这样调用这个函数的人才能得到结果。

Answer 3

如果这个列表已经排好序，那么在大O表示法上，"最有效"的方法就是用二分查找来找值，并在找到后进行前后计数。

但是，对于像例子中那样的未排序列表，唯一能计算出现次数的方法就是逐个检查每个项目（或者先把它排序 ;-）。下面是一些伪代码，注意这比原帖中的代码简单（没有使用if x in list或count[x]）：

set count to 0
for each element in the list:
   if the element is what we are looking for:
      add one to count

祝你编码愉快。