剑指37-数字在排序数组中出现的次数

Posted on | In |

题目描述

统计一个数字在排序数组中出现的次数。

  • 二分递归查找，终止条件是找到一个该数字，边界是递归函数的参数数组是空。
  • 如果找到了该数字，分别向左右遍历该数字直到不是该数字为止，计数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def GetNumberOfK(self, data, k):
        if len(data) == 0: # 如果data是空列表，返回0
            return 0
        if data[0] > data[-1]: # 按从小到大排序
            data = data[::-1]
            
        loc = len(data)>>1 # data的中间位置索引号
        if data[loc] > k: # 在左侧检查
            return self.GetNumberOfK(data[:loc], k)
        elif data[loc] < k: # 在右侧检查 
            return self.GetNumberOfK(data[loc+1:], k)
        else:
            count = 0
            for num in data[:loc][::-1]:
                if num == k:
                    count += 1
                else:
                    break
            for num in data[loc:]:
                if num == k:
                    count += 1
                else:
                    break
            return count

因为数组元素都是整数，所以可以稍微变一下，不是搜索k的两个边界位置，而是搜索k-0.5和k+0.5这两个数应该插入的位置，然后相减即可得到k值的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def GetNumberOfK(self, data, k):
        def searchInsert(nums, target):
            s, t = 0, len(nums)
            while s < t:
                m = (s + t) >> 1
                if nums[m] == target:
                    while m > 0:
                        if nums[m-1] == target:
                            m -= 1
                        else:
                            break
                    return m
                elif nums[m] > target:
                    if m == s:
                        return m
                    else:
                        t = m
                else:
                    s = m + 1
            return s
        if len(data) <= 1:
            delta = 0.0001
        else:
            delta = min(0.0001, max([data[i+1]-data[i] for i in range(0, len(data)-1)]))
        loc1 = searchInsert(data, k-0.0001)
        loc2 = searchInsert(data, k+0.0001)
        return loc2 - loc1