Total Occurrence in Python(Binar

2018-03-29  本文已影响0人  GakkiLove

Given a target integer T and an integer array A sorted in ascending order, Find the total number of occurrences of T in A.

Examples:

A = {1, 2, 3, 4, 5}, T = 3, return 1
A = {1, 2, 2, 2, 3}, T = 2, return 3
A = {1, 2, 2, 2, 3}, T = 4, return 0

class Solution(object):
  def totalOccurrence(self, array, target):
    if len(array) == 0:
      return 0    
    low = 0
    high = len(array) - 1  
    while low < high - 1:
      mid = (low + high)/2
      if array[mid] < target:
        low = mid
      else: high = mid
        
    if array[low] == target:
      left = low
    elif array[high] == target:
      left = high
    else: 
      return 0
    
    start = 0
    end = len(array) - 1
    while start < end - 1:
      mid = (start + end)/2
      if array[mid] > target:
        end = mid
      else: start = mid
        
    if array[end] == target:
      right = end
    elif array[start] == target:
      right = start
    else: 
      return 0
    
    return right - left + 1
上一篇 下一篇

猜你喜欢

热点阅读