В этой статье блога мы рассмотрим несколько методов эффективного подсчета вхождений заданного числа в целочисленный массив. Мы предоставим примеры кода для каждого метода, что позволит вам понять и реализовать их в ваших собственных проектах. К концу этой статьи вы получите полное представление о различных методах решения этой распространенной проблемы программирования.

Метод 1: линейный поиск
Самый простой подход — перебирать массив и подсчитывать вхождения заданного числа. Вот пример реализации на Python:

def count_occurrences_linear(arr, num):
    count = 0
    for element in arr:
        if element == num:
            count += 1
    return count

Метод 2: использование класса Counter (Python)
Класс Counter из модуля коллекций в Python предоставляет удобный способ подсчета вхождений элементов в список. Вот пример:

from collections import Counter
def count_occurrences_counter(arr, num):
    counts = Counter(arr)
    return counts[num]

Метод 3: двоичный поиск (отсортированный массив)
Если массив отсортирован, мы можем использовать двоичный поиск для эффективного подсчета вхождений. Вот пример реализации на Python:

def count_occurrences_binary(arr, num):
    left = 0
    right = len(arr) - 1
    first_index = binary_search(arr, num, left, right, True)
    last_index = binary_search(arr, num, left, right, False)
    if first_index == -1 or last_index == -1:
        return 0
    return last_index - first_index + 1
def binary_search(arr, num, left, right, find_first):
    index = -1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == num:
            index = mid
            if find_first:
                right = mid - 1
            else:
                left = mid + 1
        elif arr[mid] < num:
            left = mid + 1
        else:
            right = mid - 1
    return index

Метод 4: хэш-карта (Python)
Используя хеш-карту, мы можем подсчитать вхождения числа с линейной временной сложностью. Вот пример реализации на Python:

def count_occurrences_hashmap(arr, num):
    occurrence_map = {}
    for element in arr:
        occurrence_map[element] = occurrence_map.get(element, 0) + 1
    return occurrence_map.get(num, 0)

В этой статье мы рассмотрели несколько методов эффективного подсчета вхождений заданного числа в целочисленный массив. В зависимости от конкретных требований и характеристик вашего массива некоторые методы могут оказаться более подходящими, чем другие. Учитывая такие факторы, как размер массива, сортировка и особенности языка программирования, вы можете выбрать наиболее подходящий метод для вашего случая использования. Не забудьте проанализировать временную и пространственную сложность каждого метода, чтобы принять обоснованное решение.

Используя эти методы, вы можете эффективно подсчитывать случаи и решать аналогичные проблемы в своих проектах программирования.