## Solutions

# -*- coding:utf-8 -*-
class Solution:
def GetNumberOfK(self, data, k):
# write code here
if data is None:
return 0
num_dict = {}
for num in data:
if num in num_dict:
num_dict[num] += 1
else:
num_dict[num] = 1
if k in num_dict:
return num_dict[k]
else:
return 0
# 运行时间：26ms
# 占用内存：5736k


# -*- coding:utf-8 -*-
class Solution:
def GetFirstK(self, data, k, start, last):
if start > last:
return -1
middle = (start + last) // 2
if data[middle] == k:
if middle > 0 and data[middle - 1] == k:
last = middle - 1
else:
return middle
elif data[middle] > k:
last = middle - 1
else:
start = middle + 1

return self.GetFirstK(data, k, start, last)

def GetLastK(self, data, k, start, last):
if start > last:
return -1
middle = (start + last) // 2
if data[middle] == k:
if middle < last and data[middle + 1] == k:
start = middle + 1
else:
return middle
elif data[middle] > k:
last = middle - 1
else:
start = middle + 1

return self.GetLastK(data, k, start, last)

def GetNumberOfK(self, data, k):
# write code here
number = 0
if data is not None and len(data) > 0:
length = len(data)
first = self.GetFirstK(data, k, 0, length - 1)
last = self.GetLastK(data, k, 0, length - 1)
if first > -1 and last > -1:
number = last - first + 1
return number

# 运行时间：22ms
# 占用内存：5704k