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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
KraCuBb1u
0 / 0 / 0
Регистрация: 22.12.2013
Сообщений: 1
#1

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

22.12.2013, 16:20. Просмотров 604. Ответов 1
Метки нет (Все метки)

Даны два односвязных списка целых чисел, которые содержат одни и те же уникальные числа. Числа в списках расположены различным случайным образом. Из первого списка извлекаем один любой элемент. Нужно определить, какое число теперь отсутствует в этом списке, при условии, что на входе будут только сами эти списки. Приветствуется решение сложности O(N).
Практическая аналогия условия. Имеем две одинаковые колоды карт, причем неизвестно, для игры в дурака или, например, в преферанс предназначены эти колоды (с шестерками они или без). Колоды тасуются. После этого из одной колоды случайным образом тянем карту. Нужно определить, что за карту вытащили, имея в своем распоряжении только сами колоды.

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

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

Найти min число в списке(Динамическая память) - C++
Всем привет!! Очень прошу помочь мне с заданием. Спасибо. Написать программу, которая размещает в динамической памяти данные −...

Программа которая определяет число элементов в линейном списке - C++
Написать программу обхода бинарного дерева Нужно написать, вопросы: 1)На каком языке лучше написать? 2)И как это лучше сделать? ...

Нужно продублировать первое чётное число в односвязном списке - C++
Написал вот такой код, он рабочий, но никак не пойму, что нужно сделать, чтоб выполнялась поставленная задача. Прошу помочь. #include...

Добавить в конец непустой очереди все ее элементы, располагая их в обратном порядке - C++
Добавить в конец непустой очереди все ее элементы, располагая их в обратном порядке.

Вставить в однонаправленном списке число 1.5 после каждого элемента с отрицательным значением - C++
создать линейный однонаправленный список из вещественных чисел. вставить в список число 1.5 после каждого элемента с отрицательным...

Как определить максимум сотрудников в списке? - C++
Здравствуйте! я создал код программы с односвязным списком. #include <iostream> #include <fstream> #include <conio.h> #include...

1
Алешка96
0 / 0 / 0
Регистрация: 26.11.2014
Сообщений: 1
26.11.2014, 00:30 #2
это сложность О(n^2)
думай дальше
ответ очень прост))))
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2014, 00:30
Привет! Вот еще темы с ответами:

Определить, сколько в списке различных элементов - C++
Дан список, упорядоченный по неубыванию элементов в нем. Определите, сколько в нем различных элементов.

Сформировать двухмерный массив, располагая в нем столбцы исходного массива в порядке, заданном в 3 массиве - C++
Массив данных A размерностью MxN задано пользователем с клавиатуры вместе с параметрами M и N. Кроме того задано одномерный массив P...

Определить количество повторений каждого слова в списке - C++
Создать односвязный линейный список из слов некоторого строки, расположив их в списке по алфавиту. Определить количество повторений каждого...

Определить, сколько в списке встречается различных чисел - C++
Дан список чисел, который может содержать до 100000 чисел. Определите, сколько в нем встречается различных чисел. Помогите, пожалуйста,...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru