Найти максимальный элемент среди одинаковых элементов

@777kostet777 · Регистрация: 20.01.2015

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

Доброй ночи, помогите решить задачу по программированию в С++, программировании новичок, для меня это трудно
Даны два целочисленых массива K(m) и L(n), найти максимальный элемент среди одинаковых элементов массивов K и L
заранее спасибо

@CAXOPOK · 23.01.2015, 13:19

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

@Voivoid · 23.01.2015, 13:24

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

если надо подробней, опишу.

Ну давай

@CAXOPOK · 23.01.2015, 13:42

Начнём с того, что числа целые. Соответственно создаём два булевых массива A и B размером в весь диапазон int. Пробегаем по первому массиву K. И в A[K[i]] ставим 1. (Если есть отрицательные числа, то индекс смещаем так чтобы min_int был в массиве A под индексом 0). Аналогично для массивов L и B. Далее для соответствующих элементов A[i], B[j] находим конъюнкцию (логическое умножение), это даст нам битовую строку с одинаковыми элементами(пусть мы её сохранили в А). Далее пробегаем по этому массиву А с конца и первый индекс элемента со значением 1 и будет максимальным общим числом. Итого 2 цикла, но они не вложены. Имеет смысл на очень больших объёмах данных.
Вторая идея с сортировкой.
Что касается сортировки, то стандартный quick sort обычно работает за О(N*lnN). Поиск максимального общего будет точно не сложнее того же О(N*lnN) : в худшем случае полный перебор элементов первого массива и бинарный поиск его в другом массиве.

@Xelort · 23.01.2015, 19:42

C++
1
2
3
4
5
6
7
const int m = 5, n = 8;
    int K[m] = {10, 10, 0, 20, 5}, L[n] = {10, 20, 10, 0, 0, 1, 4, 4},max=-1;
 
    set<int> x(K, K + m);
    for (int i = 0, size = x.size(), index = 0; i < n; i++, size = x.size())
        if ((x.insert(L[i]), x.size()) == size)if (!index++)max = L[i]; else if (max < L[i])max = L[i];
    cout << max;

Добавлено через 4 минуты

C++
1
2
3
4
5
6
7
8
9
 const int m = 5, n = 8;
    int K[m] = {10, 10, 0, 12, 5}, L[n] = {10, 12, 1, 0, 0, 1, 4, 4},max=-1;
 
    std::map<int, string> map; 
    for (int i = 0, j = 0, index = 1; i < n + m; index = (++i >= m) ? 0 : 1) {
        if (index) map[K[i]] = "a"; else if (map[L[i - m ]] += "b", map[L[i - m]] == "ab")
            if (!j++ || max < L[i - m])max = L[i - m];
    }
    cout << max;

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

@777kostet777 0 / 0 / 0 Регистрация: 20.01.2015 Сообщений: 11

	Найти максимальный элемент среди одинаковых элементов 23.01.2015, 01:56. Показов 3443. Ответов 23 Метки нет (Все метки) Доброй ночи, помогите решить задачу по программированию в С++, программировании новичок, для меня это трудно Даны два целочисленых массива K(m) и L(n), найти максимальный элемент среди одинаковых элементов массивов K и L заранее спасибо 0

@CAXOPOK 2 / 2 / 0 Регистрация: 29.03.2013 Сообщений: 59
	23.01.2015, 13:19
	Вообще, если тут такой холивар, то эту задачу можно сделать не используя 2 вложенных цикла, а именно с линейной сложностью, но это будет называться костылём или чем-то подобным, если надо подробней, опишу. 0

@CAXOPOK 2 / 2 / 0 Регистрация: 29.03.2013 Сообщений: 59
	23.01.2015, 13:42
	Начнём с того, что числа целые. Соответственно создаём два булевых массива A и B размером в весь диапазон int. Пробегаем по первому массиву K. И в A[K[i]] ставим 1. (Если есть отрицательные числа, то индекс смещаем так чтобы min_int был в массиве A под индексом 0). Аналогично для массивов L и B. Далее для соответствующих элементов A[i], B[j] находим конъюнкцию (логическое умножение), это даст нам битовую строку с одинаковыми элементами(пусть мы её сохранили в А). Далее пробегаем по этому массиву А с конца и первый индекс элемента со значением 1 и будет максимальным общим числом. Итого 2 цикла, но они не вложены. Имеет смысл на очень больших объёмах данных. Вторая идея с сортировкой. Что касается сортировки, то стандартный quick sort обычно работает за О(NlnN). Поиск максимального общего будет точно не сложнее того же О(NlnN) : в худшем случае полный перебор элементов первого массива и бинарный поиск его в другом массиве. 0