剑指Offer(三十七):数字在排序数组中出现的次数

2018年1月15日21:01:16 8 2,052 °C
摘要

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

剑指Offer(三十七):数字在排序数组中出现的次数

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

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

数组data中,数字k出现的第一个位置:

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

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

2、代码

C++:

Python:

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

weinxin
微信公众号
分享技术,乐享生活:Jack Cui公众号每周五推送“程序员欢乐送”系列资讯类文章,欢迎您的关注!
Jack Cui

发表评论

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

目前评论:8   其中:访客  5   博主  3

    • avatar 发文 未知系统 谷歌浏览器 Windows 10 局域网 对方和您在同一内部网 4

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

        • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 北京市 百度网讯科技联通节点

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

        • avatar Lucas 来自天朝的朋友 QQ浏览器 Windows 10 江苏省苏州市 电信 1

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

            • avatar Lucas 来自天朝的朋友 QQ浏览器 Windows 10 江苏省苏州市 电信 1

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

                • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Windows 10 黑龙江省哈尔滨市 联通

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

              • avatar gzshan 来自天朝的朋友 火狐浏览器 Windows 10 北京市 北京电信互联网数据中心 0

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

                  • avatar Jack Cui Admin 来自天朝的朋友 谷歌浏览器 Mac OS X 10_14_4 北京市 百度网讯科技联通节点

                    @gzshan 已更正。

                  • avatar 何去何从gw 来自天朝的朋友 谷歌浏览器 Windows 10 湖北省武汉市 移动 0

                    //因为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)