Найдите, встречается ли какое-либо число в отсортированном массиве более n/4 раз
На собеседовании меня спросили следующее:
Учитывая отсортированный массив с n числами (где n кратно 4), выведите результат, появляется ли какое-либо число более n/4 раз.
Моя первоначальная мысль заключалась в том, чтобы перебрать массив и сохранить счетчик:
limit = len(nums) // 4
counter = 1
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
counter += 1
if counter > limit:
return True
else:
counter = 1
return False
Однако интервьюер спросил, могу ли я добиться большего. Сортированный массив, лучше, чем линейная сложность, я сразу подумал о «двоичном поиске»… Я исследовал этот путь, но ничего не знал.
Через несколько минут он подсказал: «если существует i, где nums[i] == nums[i + len(nums)/4]», значит ли это, что мы должны вернуть true?
Я пытался применить это к своему двоичному поиску и не соображал, поэтому подсказка пролетела мимо моей головы... Ретроспективно это тривиально, однако я вижу только, как применить это с помощью скользящего окна:
limit = len(nums) // 4
for i in range(limit, len(nums)):
if nums[i] == nums[i-limit]:
return True
return False
Это то, что имел в виду интервьюер? Или есть лучшее нелинейное решение?
Ответы 2
Число, которое встречается более n/4 раз в nums, должно быть одним из элементов nums[::len(nums)//4]. Для каждого номера-кандидата мы выполняем двоичный поиск первой позиции, где он появляется, и проверяем, появится ли тот же номер len(nums)//4 в дальнейшем:
import bisect
def check(nums):
n = len(nums)
assert n % 4 == 0
for i in nums[::n//4]:
first_appearance = bisect.bisect_left(nums, i)
if first_appearance + n//4 < len(nums) and nums[first_appearance + n//4] == i:
return True
return False
Мы выполняем не более 4 двоичных поисков и не более постоянного объема другой работы, поэтому временная сложность равна O(log n).
Поскольку массив отсортирован, если число появляется более n/4 раз, оно будет охватывать блок длиной больше n/4. Следовательно, будет хотя бы один индекс i, в котором число в позиции i совпадает с числом в позиции i + n/4.
Вместо того, чтобы перебирать каждый элемент, вы можете проверять позиции, расположенные на расстоянии n/4 друг от друга.
#Edited
def appears_more_than_n_over_4(nums):
n = len(nums)
limit = n // 4
check_positions = [0, limit, 2 * limit, 3 * limit]
for i in check_positions:
# Find the start and end of the current element
start = bisect.bisect_left(nums, nums[i])
end = bisect.bisect_right(nums, nums[i]) - 1
# Check if the count of the element exceeds the limit
if end - start + 1 > limit:
return True
return False
Это не удается на
[0, 1, 1, 1, 2, 3, 4, 5].