Sui Xin's Blog

[剑指Offer]数字在排序数组中出现的次数

Posted on In Disqus:

题目描述

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

解题思路

  1. 方法一：Python作弊法；
  2. 方法二：使用二分法查找数组中k的位置，然后向两边扩展查找共出现了多少次；
  3. 方法三：使用二分法分别查找数组中k首次出现和最后一次出现的位置。时间复杂度为$O(\log n)$。

代码

Python(2.7.3)

方法一

1
2
3
4
5
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        return data.count(k)

运行时间：24ms
占用内存：5708k

方法二

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
29
30
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        length = len(data)
        if length < 1:
            return 0
        min_idx, max_idx = 0, length - 1
        while True:
            mid_idx = (max_idx + min_idx) // 2
            if data[mid_idx] == k:
                break
            if data[mid_idx] > k:
                max_idx = mid_idx
            else:
                min_idx = mid_idx
            if max_idx - min_idx <= 1:
                return 0
        count = 0
        for i in range(mid_idx - 1, -1, -1):
            if data[i] == k:
                count += 1
            else:
                break
        for i in range(mid_idx, length):
            if data[i] == k:
                count += 1
            else:
                break
        return count

运行时间：27ms
占用内存：5732k

方法三

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
29
30
31
32
33
34
35
36
37
38
39
40
41
# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        if len(data) < 1:
            return 0
        firstk, lastk = self.getFirstK(data, k), self.getLastK(data, k)
        if firstk == -1:
            return 0
        else:
            return lastk - firstk + 1
    
    def getFirstK(self, data, k):
        min_idx, max_idx = 0, len(data) - 1
        while True:
            mid_idx = (max_idx + min_idx) // 2
            if data[mid_idx] < k:
                min_idx = mid_idx + 1
            elif data[mid_idx] > k:
                max_idx = mid_idx - 1
            elif mid_idx > 0 and data[mid_idx - 1] == k:
                max_idx = mid_idx - 1
            else:
                return mid_idx
            if max_idx < min_idx:
                return -1
        
    def getLastK(self, data, k):
        min_idx, max_idx = 0, len(data) - 1
        while True:
            mid_idx = (max_idx + min_idx) // 2
            if data[mid_idx] < k:
                min_idx = mid_idx + 1
            elif data[mid_idx] > k:
                max_idx = mid_idx - 1
            elif mid_idx < len(data) - 1 and data[mid_idx + 1] == k:
                min_idx = mid_idx + 1
            else:
                return mid_idx
            if max_idx < min_idx:
                return -1

运行时间：30ms
占用内存：5860k

Related Posts