Сложность: easy
Дан массив целых чисел, отсортированный в неубывающем порядке. В этом массиве есть ровно одно число, которое встречается более чем в 25% случаев. Верните это число.
Пример:
Input: arr = [1,2,2,6,6,6,6,7,10]
Output: 6
👨💻 Алгоритм:
1⃣Инициализируйте хеш-таблицу counts и перебирайте каждый элемент в массиве arr, увеличивая counts[num] для каждого элемента num.
2⃣Установите target = arr.length / 4.
3⃣Перебирайте каждую пару ключ-значение в counts и, если значение > target, верните ключ. Код никогда не достигнет этой точки, так как гарантируется, что ответ существует; верните любое значение.
😎 Решение:
from collections import defaultdict
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
counts = defaultdict(int)
target = len(arr) / 4
for num in arr:
counts[num] += 1
if counts[num] > target:
return num
return -1
Ставь 👍 и забирай 📚 Базу знаний