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

  • A+
所属分类:剑指Offer
摘要

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

剑指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有现成的函数供我们使用:

Jack Cui

发表评论

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