mabreuortega
BAN USERNote that the only numbers that can be the popular are 1, n/4, n/2, 3n/4, n
In this solution we are doing 8 binary search and we are using O(1) additional memory
def findPopular(items):
N = len(items)
inc = int(N/4)
i = [x*inc for x in [1, 2, 3, 4]]
n = [items[x] for x in i]
for k in range(0,len(i)):
a = i[k - 1] if k > 0 else 0
b = i[k + 1] if k + 1 < N else N -1
first = findFirst(items, a, i[k], n[k])
last = findLast(items, i[k], b, n[k])
if last - first + 1 >= inc:
return n[k]
def findFirst(items, i, j, n):
first = -1
while i <= j:
mid = int((i + j)/2)
if items[mid] < n:
i = mid + 1
else:
if items[mid] == n:
first = mid
j = mid - 1
return first
def findLast(items, i, j, n):
last = -1
while i <= j:
mid = int((i + j)/2)
if items[mid] > n:
j = mid - 1
else:
if items[mid] == n:
last = mid
i = mid + 1
return last
This is a classic!
- mabreuortega February 26, 2015