Leetcode
- Element Appearing More Than 25% In Sorted Array
class Solution(object):
def findSpecialInteger(self, arr):
"""
:type arr: List[int]
:rtype: int
"""
if len(arr) > 8:
return self.getMostFrequentNumberOptimized(arr)
return self.getMostFrequentNumber(arr)
def getMostFrequentNumber(self, arr):
counter = {}
for n in arr:
if n in counter:
counter[n] += 1
else:
counter[n] = 1
targetPercent = (len(arr) * 25)//100
for n in counter:
if counter[n] > targetPercent:
return n
def getMostFrequentNumberOptimized(self, arr):
numsCount = len(arr)
p1 = (numsCount // 4) - 1
p2 = (numsCount // 2) - 1
p3 = ((numsCount * 3) // 4) - 1
print("len=", numsCount, "p1=", p1, "p2=", p2, "p3=", p3)
print(arr[0], arr[p1], arr[p2], arr[p3], arr[-1])
if arr[0] == arr[p1]:
return arr[0]
if arr[p1] == arr[p2]:
return arr[p1]
if arr[p2] == arr[p3]:
return arr[p2]
if arr[p3] == arr[-1]:
return arr[p3]
The above optimized approach has a flaw. The offsets are fixed and the 25% spread can be across two quartets.
num = [1,2,2,2,3,4,4,5,6,6,7,7]
We need to use a sliding window of quarters.
def getMostFrequentNumberOptimized(self, arr):
n = len(arr)
offset = n/4
for i in range(n - offset):
if arr[i] == arr[i + offset]:
return arr[i]
