cafertyildirim
BAN USERI will use a usual binary search to find first occurrences of ages and then I will take the differences to find counts. Here is my Python code:
def binarySearch(arr, low, high, value):
# this is usual binary search algorithm
if high - low < 2:
if arr[low] == value:
return low
elif arr[high] == value:
return high
else:
return None
else:
mid = (low + high)/2
if arr[mid] < value:
return binarySearch(arr, mid, high, value)
else:
return binarySearch(arr, low, mid, value)
def countSorted(arr):
# using binary search I will find first occurrences of each age, I will run binary search on the rest of the array with age + 1
# I will assume there is no jump in the ages, I am not assuming any upper bound on age
firstOcc = [0]
while firstOcc[-1] != None:
firstOcc.append(binarySearch(arr,firstOcc[-1],len(arr) - 1,len(firstOcc)))
print firstOcc
return takeDiff(arr,firstOcc)
def takeDiff(arr,firstOcc):
counts = []
for i in range(len(firstOcc) - 2):
counts.append(firstOcc[i+1] - firstOcc[i])
counts.append(len(arr) - firstOcc[len(firstOcc) - 2])
return counts
arr = [0,0,1,1,1,2,3,3,3,4,4,4]
print countSorted(arr)
Python implementation
- cafertyildirim December 06, 2014