剑指Offer（三十七）：数字在排序数组中出现的次数

2018年1月15日21:01:16 10 4,900 °C
摘要

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

剑指Offer（三十七）：数字在排序数组中出现的次数

一、前言

本系列文章为《剑指Offer》刷题笔记。

刷题平台：牛客网

书籍下载：共享资源

二、题目

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

1、思路

既然是已经排序好的数组，那么第一个想到的就是二分查找法。

做法就是使用二分法找到数字在数组中出现的第一个位置，再利用二分法找到数字在数组中出现的第二个位置。时间复杂度为O(logn + logn)，最终的时间复杂度为O(logn)。

举个例子，找到数字k在数组data中出现的次数。

数组data中，数字k出现的第一个位置：

我们对数组data进行二分，如果数组中间的数字小于k，说明k应该出现在中间位置的右边；如果数组中间的数字大于k，说明k应该出现在中间位置的左边；如果数组中间的数字等于k，并且中间位置的前一个数字不等于k，说明这个中间数字就是数字k出现的第一个位置。

同理，数字k出现的最后一个位置，也是这样找的。但是判断少有不同。我们使用两个函数分别获得他们。

2、代码

C++：

C++
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int length = data.size();
        if(length == 0){
            return 0;
        }
        int first = GetFirstK(data, k, 0, length - 1);
        int last = GetLastK(data, k, 0, length - 1);
        if(first != -1 && last != -1){
            return last - first + 1;
        }
        return 0;
    }
private:
    // 迭代实现找到第一个K
    int GetFirstK(vector<int> data, int k, int begin, int end){
        if(begin > end){
            return -1;
        }
        int middleIndex = (begin + end) >> 1;
        int middleData = data[middleIndex];
        
        if(middleData == k){
            if((middleIndex > 0 && data[middleIndex - 1] != k) || middleIndex == 0){
                return middleIndex;
            }
            else{
                end = middleIndex - 1;
            }
        }
        else if (middleData > k){
            end = middleIndex - 1;
        }
        else{
            begin = middleIndex + 1;
        }
        return GetFirstK(data, k, begin, end);
    }
    // 循环实现找到最后一个K
    int GetLastK(vector<int> data, int k, int begin, int end){
        int length = data.size();
        int middleIndex = (begin + end) >> 1;
        int middleData = data[middleIndex];
        
        while(begin <= end){
            if(middleData == k){
                if((middleIndex < length - 1 && data[middleIndex + 1] != k) || middleIndex == length - 1){
                    return middleIndex;
                }
                else{
                    begin = middleIndex + 1;
                }
            }
            else if(middleData > k){
                end = middleIndex - 1;
            }
            else{
                begin = middleIndex + 1;
            }
            middleIndex = (begin + end) >> 1;
            middleData = data[middleIndex];
        }
        return -1;
    }
};

Python：

Python有现成的函数供我们使用：

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

weinxin
微信公众号
分享技术，乐享生活：微信公众号搜索「JackCui-AI」关注一个在互联网摸爬滚打的潜行者。
Jack Cui

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

目前评论：10   其中：访客  7   博主  3

    • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4
      回复 2018年7月20日 下午2:39  沙发

      不知道是降序还是升序，都可以这样写吗？
      else if (middleData > k){
      end = middleIndex – 1;

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点
          回复 2018年7月20日 下午5:16  1层

          @发文 只要是有序的，二分法就可以啊。

        • avatar Lucas 来自天朝的朋友 QQ浏览器 Windows 10 江苏省苏州市 电信 1
          回复 2019年1月30日 上午10:08  板凳

          想问下在旋转数组最小值那道题中我们直接将low和high=mid，这里low = mid + 1好像也可以直接将low = mid，两种可以比较一下吗楼主 有点理不清

            • avatar Lucas 来自天朝的朋友 QQ浏览器 Windows 10 江苏省苏州市 电信 1
              回复 2019年1月30日 下午1:50  1层

              @Lucas 自己又想了下，好像这样做在遍历到最后只有两位的时候key在后位会卡死，那里退出条件是right = low + 1才能用，还是谢谢楼主了

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通
                  回复 2019年1月30日 下午3:49  2层

                  @Lucas :wink: :wink: :wink: :wink:

              • avatar gzshan 来自天朝的朋友 火狐浏览器 Windows 10 北京市 北京电信互联网数据中心 0
                回复 2019年5月8日 下午7:21  地板

                二分查找时间复杂度应该是O(logn)吧

                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点
                    回复 2019年5月8日 下午7:40  1层

                    @gzshan 已更正。

                  • avatar 何去何从gw 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省武汉市 移动 0
                    回复 2019年8月18日 下午6:46  4楼

                    //因为data中都是整数，所以可以稍微变一下，不是搜索k的两个位置，而是搜索k-0.5和k+0.5
                    //这两个数应该插入的位置，然后相减即可。

                    class Solution:
                    def GetNumberOfK(self, data, k):
                    # write code here
                    def func(arr, k):
                    left, right = 0, len(arr)-1
                    while left >1
                    if k>arr[mid]:
                    left = mid + 1
                    else:
                    right = mid - 1
                    return left
                    return func(data, k+0.1) - func(data, k-0.1)

                    • avatar yyx 来自天朝的朋友 火狐浏览器 Ubuntu Linux 北京市 移动 2
                      回复 2019年9月3日 下午3:34  5楼

                      博主大大，我看之前有一道题《第一次只出现的字符》可以用哈希表来统计出现的次数，这道题为什么不行呀

                        • avatar yyx 来自天朝的朋友 火狐浏览器 Ubuntu Linux 北京市 移动 2
                          回复 2019年9月3日 下午4:06  1层

                          @yyx 是我弄错啦，也可以运行