【剑指Offer】数字在排序数组中出现的次数 解题报告（Python）
2024-09-02 01:41:10
【剑指Offer】数字在排序数组中出现的次数 解题报告（Python）
标签（空格分隔）： 剑指Offer
题目地址：https://www.nowcoder.com/ta/coding-interviews
题目描述：
统计一个数字在排序数组中出现的次数。
解题方法
看到有序，使用二分查找。
使用二分找到这段连续的k的最左边的位置，最右边的位置，两个相减+1就是长度了。
代码：
# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
num = 0
if data:
first = self.getFirstK(data, k , 0, len(data) - 1)
last = self.getLastK(data, k, 0, len(data) - 1)
if first > -1 and last > -1:
num = last - first + 1
return num
def getFirstK(self, data, k, start, end):
if start > end:
return -1
mid = (start + end) / 2
midD = data[mid]
if midD > k:
end = mid - 1
elif midD < k:
start = mid + 1
else:
if (mid == 0) or (mid > 0 and data[mid - 1] != k):
return mid
else:
end = mid - 1
return self.getFirstK(data, k, start, end)
def getLastK(self, data, k, start, end):
if start > end:
return -1
mid = (start + end) / 2
midD = data[mid]
if midD > k:
end = mid - 1
elif midD < k:
start = mid + 1
else:
if (mid == len(data) - 1) or (mid < len(data) - 1 and data[mid + 1] != k):
return mid
else:
start = mid + 1
return self.getLastK(data, k, start, end)#复制粘贴搞错了。。Date
2018 年 3 月 24 日 – 周六，校园里很多正在拍毕业照的研三学生～～
最新文章
- ajaxpro 异步调用
- man curl_easy_setopt（原创）
- BZOJ2733 [HNOI2012]永无乡
- alpha发布（技术随笔）
- [整理]Linux压缩与解压缩命令整理。
- NAND flash NOR flash SDRAM区别
- ceilometer
- Menu之选项菜单
- php5,Apache在windows 7环境搭建
- PC远程调试移动设备(转载)
- SpringBoot优化内嵌的Tomcat
- atitit.报告最佳实践oae 和报告引擎的选择
- 在ubuntu16.04中再次体验.net core 2.0
- 中间件方法必须返回Response对象实例(tp5.1+小程序结合时候出的问题)
- 怎么样通过php使用html5实现多文件上传？（php多图上传）
- MySQL 5.7.17 Group Relication（组复制）搭建手册【转】
- linux网口驱动实现（待续）
- flask学习(六)：URL传参
- android studio - 隐藏编辑器上面的竖线
- 【转载】JAVA中线程的两种实现方法-实现Runnable接口和继承Thread类