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

2018年1月15日21:01:16 2 506 °C
摘要

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

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

一、前言

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

刷题平台:牛客网

书籍下载:共享资源

二、题目

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

1、思路

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

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

举个例子,找到数字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:

目前评论:2   其中:访客  1   博主  1

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

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

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

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