Как посчитать количество вхождений элементов одного массива в другом?

Question

Как посчитать количество вхождений элементов одного массива в другом?

Рейтинг: 1Ответов: 2Опубликовано: 20.07.2025

Ребят, не могу найти ошибку в коде, выдает wrong answer на 4 тесте

Условие:

Даны два массива. Для каждого элемента второго массива определите, сколько раз он встречается в первом массиве. Выведите m чисел: для каждого элемента второго массива выведите, сколько раз такое значение встречается в первом массиве.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int m;
    cin >> m;
    vector<int> b(m);
    for (int i = 0; i < m; i++) {
        cin >> b[i];
    }
    sort(a.begin(), a.end());
    for (int i = 0; i < m; i++) {
        int L = -1, R = n, mid = 0, x = b[i], first = 0, ans = 0, last = 0;
        while (R - L > 1) {
            mid = (R + L) / 2;
            if (x <= a[mid]) {
                R = mid;
            } else {
                L = mid;
            }
        }
        if (a[R] == x) {
            first = R;
        } else {
            cout << 0 << endl;
            continue;
        }
        L = first, R = n + 1, mid = 0, ans = 0;
        while (R - L > 1) {
            mid = (R + L) / 2;
            if (x == a[mid]) {
                L = mid;
            } else {
                R = mid;
            }
        }
        last = L;
        ans = last - first + 1;
        cout << ans << endl;
    }
}

c# массивы алгоритм олимпиада

Источник: Stack Overflow на русском

Answer 1

▲ 3

#include <iostream>
#include <map>

using namespace std;

int main()
{
    int d, n;
    cin >> n;
    map<int,int> a;
    for (int i = 0; i < n; i++)
    {
        cin >> d;
        a[d]++;
    }
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> d;
        cout << a[d] << " ";
    }
}

не нарушает никаких условий? Или надо именно двоичный поиск и писать самому?

Answer 2

▲ 1

Вышли за границу в a[R] при R=n.

А вам рассказывали, про цикл вида for(декларация: выражение)? Упрощенная и процедурная версия вашего метода без сортировки выглядит вот так (я не писал ввод пользователя)

#include <iostream>
#include <vector>

void occurencies(const std::vector<int>& arr1, const std::vector<int>& arr2)
{    
    for (int val1 : arr1) {
        int count = 0;
        for (int val2 : arr2) {
            if (val1 == val2) {
                count++;
            }
        }
        //std::cout << "Значение " << val1 << " - " << count << "\n";
        std::cout << count << "\n";
    }
}

int main() {
    std::vector<int> array1 = {1, 2, 3, 2, 4, 5};  // TODO: замените на ввод пользователя
    std::vector<int> array2 = {2, 5, 1, 5, 6, 7};  // TODO: замените на ввод пользователя

    //std::cout << "Значения 2го массива во 1ом массиве::\n";
    occurencies(array2, array1);
    return 0;
}

Такие циклы зачастую убирают половину ошибок в коде - уже не выйти за границу диапазона, но пригодны только для случаев когда мы не меняем сам диапазон.

Что дает сортировка? Возможность осечь часть поиска. Но ценой O(ln n) за сортировку. Или нужно сортировать на выводе? Двоичный поиск же есть реализованный в библиотеке, в рамке std::map и заранее сортировать возможно и не нужно, зависит от условий задания.

Как посчитать количество вхождений элементов одного массива в другом?

Ответы