Suppose I have a sorted array, and each element may appear multiple times.
To make it simple, here is an example:
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]
The expected output is the number of each element. In this example, the results are:
number of 1 is 17 number of 2 is 6 number of 3 is 9
I want to find a solution where the algorithm time complexity is lower than \$O(n)\$. My idea is similar to binary search:
- When I meet with equal neighbour, I will jump the tail pointer by 1, by 2, by 4, etc. and at the same time, I will make cur pointer move to the tail position
- When I meet with unequal case, I will shrink the tail pointer to be in the middle of cur and tail
- The diff between cur and last element tail is the count of the current elements
Any advice on algorithm time complexity improvement, code bugs or general code style advice is appreciated.
from collections import defaultdict import random def generate_count(numbers): last_index = -1 result = defaultdict(int) cur_index = last_index + 1 tail_index = cur_index + 1 while cur_index < len(numbers): while cur_index < tail_index and cur_index < len(numbers) and tail_index < len(numbers): if numbers[cur_index] == numbers[tail_index]: pre = cur_index cur_index = tail_index tail_index += (tail_index - pre) else: tail_index = (cur_index+tail_index) / 2 result[numbers[cur_index]] = cur_index - last_index last_index = cur_index cur_index = last_index + 1 tail_index = cur_index + 1 return result if __name__ == "__main__": numbers =  for i in range(random.randint(1,20)): numbers.append(1) print 'number of 1 is', i+1 for i in range(random.randint(1, 20)): numbers.append(2) print 'number of 2 is', i+1 for i in range(random.randint(1, 20)): numbers.append(3) print 'number of 3 is', i+1 print numbers print generate_count(numbers)