怎样在排序数组中查找数字-创新互联
这期内容当中小编将会给大家带来有关怎样在排序数组中查找数字，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。
题目:
统计一个数字在排序数组中出现的次数. 例如输入排序数组{1,2,3,3,3,3,4,5},由于3在这个数中出现了4次,输出4.
# -*- coding: utf-8 -*- # @Time : 2019-07-13 15:10 # @Author : Jayce Wong # @ProjectName : job # @FileName : getNumberOfK.py # @Blog : https://blog.51cto.com/jayce1111 # @Github : https://github.com/SysuJayce def getFirstK(data, k): start, end = 0, len(data) - 1 while start <= end: mid = (start + end) >> 1 if data[mid] == k: # 关键在于，如果mid是k，那么就判断前一个元素是不是也是k，如果是，说明这个位置不是 # 第一次出现，要在左边继续查找。否则，直接返回mid，因为是第一次出现了 if mid - 1 >= start and data[mid - 1] == k: end = mid - 1 else: return mid elif data[mid] < k: start = mid + 1 else: end = mid - 1 return -1 def getLastK(data, k): start, end = 0, len(data) - 1 while start <= end: mid = (start + end) >> 1 if data[mid] == k: if mid + 1 <= end and data[mid + 1] == k: start = mid + 1 else: return mid elif data[mid] < k: start = mid + 1 else: end = mid - 1 return -1 def getNumberOfK(data, k): """ 要获取一个有序数组中某个元素出现的次数，最直观的做法就是遍历整个数组，然后统计该元素的出现次数， 这样做的时间复杂度是O(n) 但是由于这个数组是有序的，我们可以考虑利用二分查找的方法来解决这个问题。 如果我们先利用二分查找定位到了这个元素，然后再往前往后遍历，这样的话时间复杂度也还是O(n)。 但是如果我们在利用二分查找的时候，想办法定位这个元素第一次出现的下标和最后一次出现的下标。 在利用二分查找找到一个这个元素之后，判断这个元素是否是第一个，也就是对比这个元素的前一个是否也 是k，如果不是，说明这个元素就是第一个元素，否则在这个下标的左边继续查找。 对于最后一次出现的下标同理。 """ if not data: return 0 first = getFirstK(data, k) last = getLastK(data, k) if first != -1 and last != -1: return last - first + 1 else: return 0 def main(): data = [1, 2, 3, 3, 3, 3, 4, 5] k = 3 print(getNumberOfK(data, k)) if __name__ == '__main__': main()
上述就是小编为大家分享的怎样在排序数组中查找数字了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。
另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
本文名称：怎样在排序数组中查找数字-创新互联
标题URL：http://ybzwz.com/article/decpoh.html
