1

Всем привет, есть такая задача: задано два одномерных массива, одинаковой размерности. Определить количество одинаковых элементов в двух заданных массивах.

Пример входных данных:

A[5] = {2, 0, 4, 12, 7}

В[5] = {0, 1, 7, 7, 5}

Output: 5 Так как одинаковые элементы 0, 0, 7, 7, 7 тогда их количество равняется 5.

А моя программа, к сожалению, выводит количество совпадений и я не знаю как это исправить.

P.S. массив может быть любой размерности, я думаю стоит использовать динамические массивы

#include <iostream>

using namespace std;

int main() {
    int n, count = 0;
    cout << "Enter size of array:";
    cin >> n;
    int* arr1 = new int[n];
    int* arr2 = new int[n];
    cout << "Enter elements of arr1:";
    for (int i = 0; i < n; i++) {
        cin >> arr1[i];
    }
    cout << "Enter elements of arr2:";
    for (int i = 0; i < n; i++) {
        cin >> arr2[i];
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (arr1[i] = arr2[j]) {
                count++;
            }
        }
    }
    cout << count;
}
1
  • Нужно учитывать только такие повторы, которые есть в обоих массивах? Т.е. если в первом не будет 7, то пару семёрок из второго считать или нет?
    – MBo
    5 ноя 2021 в 16:39

1 ответ 1

3

Чтобы оптимизировать поиск, можно произвести сортировку данных массивов и последущий бинарный поиск каждого элемента наименьшего по размеру массива во втором. Таким образом сложность составит 2 * O(n*log(n)) + n * O(log(n)), что намного быстрее, чем O(n^2) Если функция бинарного поиска возвращает отрицательное значение, тогда такого элемента во втором списке нет, а если неотрицательное, тогда инкрементируем счетчик.

2
  • 2
    Я думаю, проще и быстрее последовательно сравнивать массивы после сортировки (действия примерно такие же, как при слиянии 2-х отсортированных массивов в сортировке слиянием)
    – avp
    6 ноя 2021 в 21:06
  • 1
    Спасибо!!!!!!!!
    – Иван
    10 ноя 2021 в 19:28

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.