Найти пересечение массивов

@Avgust · Регистрация: 03.11.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте. Работаю с массивами. Есть 2 массива и нужно найти их пересечение. Проблема: если есть 2 или более соответствий, то есть в mas1={1,3} а в mas2={4,3,3}, то у меня получается найти их пересечение - 3. Но и вывожу я его 2 раза. Как от этого избавиться, подскажите пожалуйста. То есть нужно, чтобы 3 выводилось только 1 раз. Массивы вводятся с клавиатуры, это для примера привел. Помогите кто может)

@notfedov · 15.05.2015, 00:37

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

@Nosey · 15.05.2015, 01:04

http://en.cppreference.com/w/c... tersection

@notfedov · 15.05.2015, 01:29

Nosey,

in both sorted ranges [first1, last1) and [first2, last2)...

не подходит. У нас входные данные могут быть неотсортированы.

@Renji · 15.05.2015, 01:33

Сначала загоняем массивы в std::set, потом смотрим пересечение сетов.

Tulosba · 15.05.2015, 06:32

Avgust, если проблема только в многократном выводе (а остальное уже реализовано), то перед выводом проверяй число, было ли оно уже выведено.

@Nosey · 15.05.2015, 09:22

notfedov, Ну так отсортируйте

Сложность алгоритма от этого не увеличится)

Tulosba · 15.05.2015, 09:49

Сообщение от Nosey

Ну так отсортируйте

А если нужно сохранить порядок?

Сообщение от Nosey

Сложность алгоритма от этого не увеличится)

Не факт. Надо смотреть по итогам реализации.

@Nosey · 15.05.2015, 10:07

Сообщение от Tulosba

А если нужно сохранить порядок?

Ну тут руками, да.

Сообщение от Tulosba

Не факт. Надо смотреть по итогам реализации.

Ну при равных алгоритмах не изменится, уж алгоритмическая сложность - точно. ( в которой 2N и N - считается одинаковой сложностью и в 99% случаев сия разница не заметна)

Tulosba · 15.05.2015, 10:54

Сообщение от Nosey

в которой 2N и N - считается одинаковой сложностью

С точки зрения O-нотации безусловно. Только вот, если алгоритм начинает работать в 2 раза дольше, это как-раз таки может быть заметно. Пример: 3D шутер выдавал 100FPS, и вдруг провалился до 50. В динамике сразу ощутимо.

@Avgust · 15.05.2015, 11:27 **[ТС]**

Сообщение от Renji

Сначала загоняем массивы в std::set, потом смотрим пересечение сетов.

щас пока про set почитаю, спасибо, вроде адекватный вариант)

Сообщение от Tulosba

Avgust, если проблема только в многократном выводе (а остальное уже реализовано), то перед выводом проверяй число, было ли оно уже выведено.

а как это, проверять, выводил я это число или нет, не особо понимаю) а если я его выводил уже раньше, в другом пункте проги, то оно не выведется?

Tulosba · 15.05.2015, 11:35

Сообщение от Avgust

а как это, проверять, выводил я это число или нет, не особо понимаю)

Очевидно надо где-то запомнить это, например в том же std::set (или std::unordered_set), чтобы потом искать быстро.

Сообщение от Avgust

а если я его выводил уже раньше, в другом пункте проги, то оно не выведется?

Как напишешь в программе, так и будет. Сделаешь для каждого пункта свою "память" - будет отдельно. Сделаешь общую - иначе.

@Avgust · 15.05.2015, 17:50 **[ТС]**

В общем с Set было сложно, решил делать по другому)

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void cross(int *A, int n, int *B, int m)
{
    cout << "Общие элементы:\n";
    int sizeC = 0;
    int *C = new int[sizeC];
    int max, count;
    if (n > m)
        max = n;
    else max = m;
    for (int i = 0; i < n; i++)  // тут заполнил массив всеми числами, что повторяются
        for (int j = 0; j < m; j++)
        if (A[i] == B[j])
        {
            C[i] = B[j];
            sizeC++;
        }
    for (int i = 0; i < sizeC; i++) // тут проверяю на наличие одинаковых элементов в массиве
    {
        int temp = C[i];
 
        for (int j = 0; j < sizeC; j++)
            if (temp == C[j])
                count++;
        if (count == 1)
            cout << temp << " ";
        count = 0;
    }
}

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

@Eva Rosalene · 15.05.2015, 17:55

Сообщение от Avgust

Проблема в том, что он где-то зацикливается

Проблема как минимум в том, что

C++
1
2
int sizeC = 0;
int *C = new int[sizeC];

Создаёт массив на 0 элементов и не перевыдялет под него память, например, в случае с

C++
1
++sizeC;

(К слову, такое new type[0]; вообще приводит к неопределённому поведению)

@Avgust · 15.05.2015, 18:01 **[ТС]**

Сообщение от Avgust

sizeC++;

думал можно увеличить размер массива с помощью этого)

Tulosba · 15.05.2015, 18:01

Сообщение от FraidZZ

такое new type[0]; вообще приводит к неопределённому поведению

Ну нет же. Обсуждали ведь совсем недавно. Приводит последующее разыменовывание, а не сама запись.

@Eva Rosalene · 15.05.2015, 18:05

Tulosba, собственно, это я и имел в виду.

Tulosba · 15.05.2015, 18:11

Сообщение от FraidZZ

собственно, это я и имел в виду.

Но из текста всё же это не следует. К UB приводит любой выход за диапазон выделенной памяти, и 0 элементов тут вовсе не являются особым случаем.

@Eva Rosalene · 15.05.2015, 18:15

Не по теме:

Tulosba, я бы всё же выделил его как особый. Ибо обращение по любому индексу к массиву из 0 элементов - уже UB.

Tulosba · 15.05.2015, 18:40

Не по теме:

FraidZZ, особый случай, имхо, требует особой обработки. В данном случае всё можно обобщить единым условием:

C++
1
if( i < len ) use a[i];

Поэтому я и не считаю это каким-то особым случаем.

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@Avgust 3 / 3 / 3 Регистрация: 03.11.2014 Сообщений: 80

	Найти пересечение массивов 14.05.2015, 23:35. Показов 7292. Ответов 19 Метки нет (Все метки) Здравствуйте. Работаю с массивами. Есть 2 массива и нужно найти их пересечение. Проблема: если есть 2 или более соответствий, то есть в mas1={1,3} а в mas2={4,3,3}, то у меня получается найти их пересечение - 3. Но и вывожу я его 2 раза. Как от этого избавиться, подскажите пожалуйста. То есть нужно, чтобы 3 выводилось только 1 раз. Массивы вводятся с клавиатуры, это для примера привел. Помогите кто может) 0

@notfedov 2 / 2 / 5 Регистрация: 24.02.2015 Сообщений: 10
	15.05.2015, 00:37
	Avgust, проведите дополнительную проверку на то, что уже добавили в пересечение данный элемент. 0

@Nosey 1379 / 406 / 144 Регистрация: 22.10.2014 Сообщений: 872
	15.05.2015, 01:04
	http://en.cppreference.com/w/c... tersection 0

@Renji 2784 / 1937 / 570 Регистрация: 05.06.2014 Сообщений: 5,602
	15.05.2015, 01:33
	Сначала загоняем массивы в std::set, потом смотрим пересечение сетов. 0

Tulosba :) 4773 / 3267 / 497 Регистрация: 19.02.2013 Сообщений: 9,046
	15.05.2015, 06:32
	Avgust, если проблема только в многократном выводе (а остальное уже реализовано), то перед выводом проверяй число, было ли оно уже выведено. 0

@Nosey 1379 / 406 / 144 Регистрация: 22.10.2014 Сообщений: 872
	15.05.2015, 09:22
	notfedov, Ну так отсортируйте Сложность алгоритма от этого не увеличится) 0

@Eva Rosalene Модератор 5241 / 2115 / 416 Регистрация: 06.01.2013 Сообщений: 4,846
	15.05.2015, 18:05
	Tulosba, собственно, это я и имел в виду. 0

@Eva Rosalene
	15.05.2015, 18:15
	Не по теме: Tulosba, я бы всё же выделил его как особый. Ибо обращение по любому индексу к массиву из 0 элементов - уже UB. 0