Форум программистов, компьютерный форум CyberForum.ru

Определить недостающее число в списке, располагая идентичным. - C++

Восстановить пароль Регистрация
 
KraCuBb1u
0 / 0 / 0
Регистрация: 22.12.2013
Сообщений: 1
22.12.2013, 16:20     Определить недостающее число в списке, располагая идентичным. #1
Даны два односвязных списка целых чисел, которые содержат одни и те же уникальные числа. Числа в списках расположены различным случайным образом. Из первого списка извлекаем один любой элемент. Нужно определить, какое число теперь отсутствует в этом списке, при условии, что на входе будут только сами эти списки. Приветствуется решение сложности O(N).
Практическая аналогия условия. Имеем две одинаковые колоды карт, причем неизвестно, для игры в дурака или, например, в преферанс предназначены эти колоды (с шестерками они или без). Колоды тасуются. После этого из одной колоды случайным образом тянем карту. Нужно определить, что за карту вытащили, имея в своем распоряжении только сами колоды.

Вопрос таков,ниже будет описан алгоритм решения этой задачи,правильно ли я решил задачу,задача сложности O(N) или нет? какие ещё есть способы помимо моего.(з.ы,код писать не буду т.к не уверен в правильности решения)

ВОТ АЛГОРИТМ.
Беру первый элемент первого списка - сравниваю его с каждым элементом второго списка, если элементы равны между собой - удаляю узел со второго списка дальше сравниваю второй элемент первого списка со всеми второго и т.д . Когда в первом списке я обошел все элементы я проверяю второй список на наличие узлов, если узел есть - тогда это тот, который удалили с первого cписка(это и будет решения задачи).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
22.12.2013, 16:20     Определить недостающее число в списке, располагая идентичным.
Посмотрите здесь:

C++ Найти min число в списке(Динамическая память)
C++ Добавить в конец непустой очереди все ее элементы, располагая их в обратном порядке
C++ Дано натуральное четырехзначное число n. Определить, является ли это число перевертышем
Программа которая определяет число элементов в линейном списке C++
Определить встречается ли значение i-го элемента еще раз в односвязном списке C++
Нужно продублировать первое чётное число в односвязном списке C++
Как определить максимум сотрудников в списке? C++
C++ Дано трицифровое число.Определить имеет ли число одинаковые первую и последнюю цифры

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Алешка96
0 / 0 / 0
Регистрация: 26.11.2014
Сообщений: 1
26.11.2014, 00:30     Определить недостающее число в списке, располагая идентичным. #2
это сложность О(n^2)
думай дальше
ответ очень прост))))
Yandex
Объявления
26.11.2014, 00:30     Определить недостающее число в списке, располагая идентичным.
Ответ Создать тему
Опции темы

Текущее время: 21:21. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru