题目描述:统计一个数字在排序数组中出现的次数。

Solutions

遍历一遍数组,使用字典统计每一个数字出现的次数,但是 $O(n)$ 的解法不是很令人满意。

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if data is None:
            return 0
        num_dict = {}
        for num in data:
            if num in num_dict:
                num_dict[num] += 1
            else:
                num_dict[num] = 1
        if k in num_dict:
            return num_dict[k]
        else:
            return 0
# 运行时间:26ms
# 占用内存:5736k

那么一般来说还想提速只能是往 $\log n$ 的方向上优化了,我们可以借鉴二分法的思路来做,但是其中比较棘手的是我们找到等于 k 的位置,但是不知道其是否是连续相同 k 序列的两头位置还是中间的位置,而我们需要得到两端位置,相减就能得到结果。

# -*- coding:utf-8 -*-
class Solution:
    def GetFirstK(self, data, k, start, last):
        if start > last:
            return -1
        middle = (start + last) // 2
        if data[middle] == k:
            if middle > 0 and data[middle - 1] == k:
                last = middle - 1
            else:
                return middle
        elif data[middle] > k:
            last = middle - 1
        else:
            start = middle + 1
            
        return self.GetFirstK(data, k, start, last)
    
    def GetLastK(self, data, k, start, last):
        if start > last:
            return -1
        middle = (start + last) // 2
        if data[middle] == k:
            if middle < last and data[middle + 1] == k:
                start = middle + 1
            else:
                return middle
        elif data[middle] > k:
            last = middle - 1
        else:
            start = middle + 1
            
        return self.GetLastK(data, k, start, last)
    
    def GetNumberOfK(self, data, k):
        # write code here
        number = 0
        if data is not None and len(data) > 0:
            length = len(data)
            first = self.GetFirstK(data, k, 0, length - 1)
            last = self.GetLastK(data, k, 0, length - 1)
            if first > -1 and last > -1:
                number = last - first + 1
        return number
    
# 运行时间:22ms
# 占用内存:5704k

References

  1. 038. 数字在排序数组中出现的次数