Суть задачи и прямой ответ
Подсчёт вхождений элемента в массиве — это линейный обход всех элементов с инкрементом счётчика при каждом совпадении. Алгоритм работает за O(n) по времени и O(1) по дополнительной памяти. Никакой предварительной сортировки или вспомогательных структур не требуется.
Минимальная рабочая реализация:
C:
#include <stdio.h>
int count_occurrences(const int *arr, size_t n, int target)
{
int count = 0;
for (size_t i = 0; i < n; i++) {
if (arr[i] == target) {
count++;
}
}
return count;
}
int main(void)
{
int data[] = {3, 7, 2, 7, 1, 7, 4, 7};
size_t len = sizeof(data) / sizeof(data[0]);
int target = 7;
int result = count_occurrences(data, len, target);
printf("Элемент %d встречается %d раз(а)\n", target, result);
return 0;
}Вывод программы:
Код:
Элемент 7 встречается 4 раз(а)Почему именно линейный обход
Для несортированного массива не существует способа узнать количество вхождений, не проверив каждый элемент. Любая оптимизация ниже O(n) невозможна без предварительной подготовки данных (сортировки, хеш-таблицы, частотного массива). Если задача одноразовая — линейный проход оптимален.
Если же подсчёт выполняется многократно для разных значений, имеет смысл один раз построить частотную таблицу и затем отвечать на запросы за O(1). Но это уже другая структура данных и другой компромисс по памяти.
Разбор механики по шагам
Передача массива в функцию
В C массив при передаче в функцию неявно преобразуется в указатель на первый элемент. Это означает, что внутри функции
sizeof(arr) вернёт размер указателя, а не размер массива. Поэтому размер всегда передаётся отдельным параметром.
C:
/* arr внутри функции — это указатель, не массив */
int count_occurrences(const int *arr, size_t n, int target)Ключевое слово
const в сигнатуре гарантирует, что функция не модифицирует исходные данные. Это не влияет на производительность, но делает контракт явным и позволяет компилятору выдавать предупреждения при случайной записи.Тип счётчика и индекса
Индекс объявлен как
size_t — беззнаковый тип, способный представить размер любого объекта в памяти. Это защищает от переполнения при работе с большими массивами на 64-битных платформах, где int ограничен 2^31 − 1.Счётчик
count имеет тип int. Теоретически количество вхождений не может превысить n, поэтому если n больше INT_MAX, счётчик тоже должен быть size_t. На практике для учебных задач int достаточно, но в production-коде безопаснее:
C:
size_t count_occurrences(const int *arr, size_t n, int target)
{
size_t count = 0;
for (size_t i = 0; i < n; i++) {
if (arr[i] == target) {
count++;
}
}
return count;
}Условие сравнения
Оператор
== для целочисленных типов работает предсказуемо. Для чисел с плавающей запятой прямое сравнение ненадёжно из-за ошибок округления — об этом ниже в отдельном разделе.Граничные случаи
| Ситуация | Ожидаемый результат | Что происходит в коде |
|---|---|---|
Пустой массив (n == 0) | 0 | Цикл не выполняется ни разу |
| Элемент отсутствует | 0 | Ни одно сравнение не даёт true |
Все элементы равны target | n | Счётчик инкрементируется на каждой итерации |
| Один элемент, совпадает | 1 | Одна итерация, одно совпадение |
| Один элемент, не совпадает | 0 | Одна итерация, совпадения нет |
Проверка на пустой массив не требует отдельного
if перед циклом: при n == 0 условие i < n ложно с самого начала, и тело цикла не выполняется. Это корректное поведение без дополнительных ветвлений.Подсчёт вхождений для чисел с плавающей запятой
Прямое сравнение
double через == допустимо только если значения получены одинаковым путём (например, присвоены из одной константы). Если значения являются результатом вычислений, накопленная ошибка округления делает точное сравнение бессмысленным.Стандартный приём — сравнение с допуском (epsilon):
C:
#include <stdio.h>
#include <math.h>
size_t count_occurrences_double(const double *arr, size_t n,
double target, double epsilon)
{
size_t count = 0;
for (size_t i = 0; i < n; i++) {
if (fabs(arr[i] - target) <= epsilon) {
count++;
}
}
return count;
}
int main(void)
{
double data[] = {0.1 + 0.2, 0.3, 0.30000000001, 0.5};
size_t len = sizeof(data) / sizeof(data[0]);
double target = 0.3;
double eps = 1e-9;
size_t result = count_occurrences_double(data, len, target, eps);
printf("Значений, близких к %.2f: %zu\n", target, result);
return 0;
}Здесь
0.1 + 0.2 в представлении IEEE 754 не равно 0.3 в точности, но разница меньше 1e-9, поэтому все три первых элемента засчитываются.Выбор
epsilon зависит от контекста: для финансовых расчётов допуск может быть 1e-6, для физических симуляций — 1e-12 и меньше. Универсального значения не существует.Подсчёт вхождений каждого элемента (частотная таблица)
Если нужно узнать количество вхождений не одного конкретного значения, а всех различных элементов, линейный обход с одним счётчиком не подходит. Для целочисленных значений в ограниченном диапазоне используется частотный массив:
C:
#include <stdio.h>
#include <string.h>
int main(void)
{
int data[] = {2, 5, 2, 3, 5, 2, 1, 5};
size_t len = sizeof(data) / sizeof(data[0]);
/* Предполагаем, что значения в диапазоне [0, 9] */
int freq[10];
memset(freq, 0, sizeof(freq));
for (size_t i = 0; i < len; i++) {
if (data[i] >= 0 && data[i] < 10) {
freq[data[i]]++;
}
}
for (int v = 0; v < 10; v++) {
if (freq[v] > 0) {
printf("%d -> %d раз(а)\n", v, freq[v]);
}
}
return 0;
}Вывод:
Код:
1 -> 1 раз(а)
2 -> 3 раз(а)
3 -> 1 раз(а)
5 -> 3 раз(а)Ограничения подхода:
- Диапазон значений должен быть известен заранее и умещаться в разумный объём памяти.
- Отрицательные значения требуют смещения индекса.
- Для произвольных
intбез ограничения диапазона частотный массив не подходит — нужна хеш-таблица или сортировка с последующим подсчётом серий.
Типичные ошибки
Забытый размер массива
C:
/* ОШИБКА: sizeof(arr) внутри функции даёт размер указателя */
int bad_count(const int arr[], int target)
{
int count = 0;
size_t n = sizeof(arr) / sizeof(arr[0]); /* n == 1 или 2, а не реальная длина */
for (size_t i = 0; i < n; i++) {
if (arr[i] == target) count++;
}
return count;
}Компилятор обычно не выдаёт ошибку, но результат будет неверным. Всегда передавайте размер явно.
Выход за границы массива
Если
n больше реального количества элементов, цикл читает память за пределами массива. Это неопределённое поведение: программа может вернуть мусорное значение, упасть с segfault или «случайно» работать корректно.Переполнение счётчика при int
Если массив содержит более 2^31 − 1 элементов (что возможно на 64-битной системе с большим объёмом RAM), счётчик типа
int переполнится. Используйте size_t для счётчика, если размер массива не ограничен заранее.Сравнение указателей вместо значений
C:
/* ОШИБКА: сравниваются адреса, а не содержимое */
if (&arr[i] == &target) { ... }Такая ошибка встречается редко, но возможна при копировании кода с поиском по ссылке.
Проверка результата
Простейший способ убедиться в корректности — сравнить результат с ручным подсчётом на небольшом тестовом массиве. Для автоматизации:
C:
#include <stdio.h>
#include <assert.h>
size_t count_occurrences(const int *arr, size_t n, int target);
int main(void)
{
int a[] = {1, 2, 3, 2, 2, 4};
assert(count_occurrences(a, 6, 2) == 3);
assert(count_occurrences(a, 6, 5) == 0);
assert(count_occurrences(a, 0, 2) == 0);
int all_same[] = {7, 7, 7, 7};
assert(count_occurrences(all_same, 4, 7) == 4);
printf("Все тесты пройдены\n");
return 0;
}assert прерывает программу при несовпадении, что удобно на этапе разработки. В релизных сборках assert отключается макросом NDEBUG, поэтому для production-тестирования лучше использовать отдельный тестовый фреймворк или хотя бы условный вывод.Сложность и ограничения
| Параметр | Значение |
|---|---|
| Временная сложность | O(n) — один проход по массиву |
| Пространственная сложность | O(1) — только счётчик и индекс |
| Предпосылки | Массив инициализирован, размер известен |
| Ограничения | Для несортированного массива быстрее невозможно |
| Масштабируемость | Линейная: удвоение размера удваивает время |
Если массив отсортирован, можно найти первое и последнее вхождение бинарным поиском за O(log n) и вычесть индексы. Но это требует предварительной сортировки, которая сама по себе стоит O(n log n).
Когда линейного подсчёта недостаточно
- Многократные запросы к одному и тому же массиву для разных значений — стройте частотную таблицу или хеш-таблицу один раз, затем отвечайте за O(1).
- Потоковая обработка — если данные приходят по одному элементу и массив не хранится целиком, поддерживайте счётчик на лету.
- Очень большие данные — если массив не помещается в кэш процессора, линейный обход упирается в пропускную способность памяти. В таких случаях помогают SIMD-инструкции или параллельный обход, но это уже выходит за рамки базового алгоритма.
Для подавляющего большинства задач на C — учебных, встроенных, системных — одного линейного прохода со счётчиком достаточно. Алгоритм тривиален, но именно в нём чаще всего допускают ошибки с размером массива и типами, поэтому явная передача
n и использование size_t должны быть привычкой.