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

единственный проход по массиву - C++

Восстановить пароль Регистрация
 
anzhelika
 Аватар для anzhelika
1 / 1 / 0
Регистрация: 22.09.2010
Сообщений: 31
24.11.2010, 23:05     единственный проход по массиву #1
здравствуйте, уважаемые программисты.)
у меня такой вопросик: дан массив из нечетного кол-ва элементов, каждый из который встречается в массиве 2 раза, кроме одного элемента. как это осуществить за один проход по массиву в цикле?

Добавлено через 14 минут
т.е. найти нужно этот элемент, встречающийся 1 раз за 1 проход по массиву. вот)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.11.2010, 23:05     единственный проход по массиву
Посмотрите здесь:

C++ проход по лабиринту
C++ Проход по квадрату
C++ Проход по массиву и удаление одинаковых слов
Проход лабиринта в C++ C++
C++ Проход по массиву
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
24.11.2010, 23:11     единственный проход по массиву #2
В общем случае?

Создать set<int>, при проходе по массиву, если значение не найдено в set<int> добавить его туда, если уже найдено, то удалить. В конце, в set<int> будет всего один элемент, тот который встречается в массиве всего один раз.

Решение №2:
завести переменную int hash=0;
для каждого элемента массива, xor-ить его с hash: hash ^= a[i];
в конце, hash будет равен элементу массива, который встречается только один раз
anzhelika
 Аватар для anzhelika
1 / 1 / 0
Регистрация: 22.09.2010
Сообщений: 31
24.11.2010, 23:15  [ТС]     единственный проход по массиву #3
в общем случае.
вообще, это мне задали по дискретке. только я не могу понять, что такое set<int>?? не припомню такого в курсе с++.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
24.11.2010, 23:27     единственный проход по массиву #4
посмотри второй вариант

Добавлено через 1 минуту
вот тебе для саморазвития ссылка на set: http://cplusplus.com/reference/stl/set/. но во втором варианте это тебе не нужно.
Yandex
Объявления
24.11.2010, 23:27     единственный проход по массиву
Ответ Создать тему
Опции темы

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