问题：统计一个数字在排序数组中出现的次数，输出统计后的次数。

原理：

一个直观的解法就是扫描序列统计出指定数字的个数，但这个思路并没有用上序列是排序的情况。如果序列是排序的，我们先找出该数字在序列中的区间，那么区间的长度就是数字出现的次数。那么如何找出给定数字在序列中的区间呢？有两种思路：

（1）使用双指针，序列前后同时扫描
（2）使用二分查找，分表找到数字的前后边界

思路一的时间复杂度是O(n)，思路二的时间复杂度为O(logn)。

实现：

先实现思路一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def number_of_sequence(sequence, number):
    n = len(sequence)

    i = 0
    for item in sequence:
        if item == number:
            break
        i += 1

    j = 0
    for item in reversed(sequence):
        if item == number:
            break
        j += 1
    return n - i - j

实现思路二：

我们先实现找出第一个给定数的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def get_first_k(sequence, n, k, start, end):
    if start > end:
        return -1
    middle_index = (start+end) // 2
    middle_number = sequence[middle_index]

    if middle_number == k:
        if (middle_index > 0 and sequence[middle_index-1] != k) or middle_index == 0:
            return middle_index
        else:
            end = middle_index - 1
    elif middle_number > k:
        end = middle_index - 1
    else:
        start = middle_index + 1
    return get_first_k(sequence, n, k, start, end)

类似地，找出最后一个给定数的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def get_last_k(sequence, n, k, start, end):
    if start > end:
        return -1
    middle_index = (start+end) // 2
    middle_number = sequence[middle_index]

    if middle_number == k:
        if (middle_index < n - 1 and sequence[middle_index+1] != k) or middle_index == n-1:
            return middle_index
        else:
            start = middle_index + 1
    elif middle_number < k:
        start = middle_index + 1
    else:
        end = middle_index - 1
    return get_last_k(sequence, n, k, start, end)

利用上述试下的函数找到给定数字的边界索引，从而确定数字的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def get_number_of_k(sequence, k):
    if not sequence:
        return 0
    n = len(sequence)
    first = get_first_k(sequence, n, k, 0, n-1)
    end = get_last_k(sequence, n, k, 0, n-1)

    print(first, end)
    if first > -1 and end > -1:
        return end - first + 1
    else:
        return 0

def main():
    import random
    seq = [random.choice(range(100)) for _ in range(2000)]
    seq.sort()
    print(seq)
    k = random.choice(seq)
    n = get_number_of_k(seq, k)
    print(n)
    print(seq.count(k))

使用Python中list.count函数来检验结果。