这期内容当中小编将会给大家带来有关怎样在排序数组中查找数字，文章内容丰富且以专业的角度为大家分析和叙述，阅读完这篇文章希望大家可以有所收获。
目前累计服务客户1000+，积累了丰富的产品开发及服务经验。以网站设计水平和技术实力，树立企业形象，为客户提供成都网站设计、网站建设、网站策划、网页设计、网络营销、VI设计、网站改版、漏洞修补等服务。成都创新互联始终以务实、诚信为根本，不断创新和提高建站品质，通过对领先技术的掌握、对创意设计的研究、对客户形象的视觉传递、对应用系统的结合，为客户提供更好的一站式互联网解决方案，携手广大客户，共同发展进步。
题目:
统计一个数字在排序数组中出现的次数. 例如输入排序数组{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()
上述就是小编为大家分享的怎样在排序数组中查找数字了，如果刚好有类似的疑惑，不妨参照上述分析进行理解。如果想知道更多相关知识，欢迎关注创新互联行业资讯频道。
