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

Метод поиска по массиву уникальных чисел за один проход - C++

Восстановить пароль Регистрация
 
ffgg
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 3
10.07.2014, 14:28     Метод поиска по массиву уникальных чисел за один проход #1
Подскажите какой-нибудь интересный метод поиска по массиву для данного случая:
Есть массив {1, 1, 2, 3, 3};
Надо найти неповторяющееся число (в данном случае это 2) за один проход по циклу.
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.07.2014, 14:28     Метод поиска по массиву уникальных чисел за один проход
Посмотрите здесь:

C++ Сортировка массива за один проход
единственный проход по массиву C++
C++ Проход по массиву и удаление одинаковых слов
C++ Проход по массиву
Генерация уникальных чисел C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2014, 14:31     Метод поиска по массиву уникальных чисел за один проход #2
массив отсортирован?
ffgg
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 3
10.07.2014, 14:43  [ТС]     Метод поиска по массиву уникальных чисел за один проход #3
Цитата Сообщение от Kukurudza Посмотреть сообщение
массив отсортирован?
Нет.
Kverter
 Аватар для Kverter
35 / 35 / 16
Регистрация: 30.10.2013
Сообщений: 211
10.07.2014, 14:54     Метод поиска по массиву уникальных чисел за один проход #4
А если сначала загнать весь массив в строку и брать каждый элемент массива и с помощью strrchr возвращать индекс последнего вхождения символа и индекс первого вхождения strchr, сравнивать с индексом в массиве? Так не покатит?
Kukurudza
104 / 85 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2014, 14:59     Метод поиска по массиву уникальных чисел за один проход #5
это О(n2)
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,307
10.07.2014, 15:09     Метод поиска по массиву уникальных чисел за один проход #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Вот что пришло в голову:
C++
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
using namespace std;
 
int main()
{
    int data[] = {1, 1, 2, 3, 3};
    int k = 0;
    for(auto i: data)
        k ^= i;
    cout << k << endl;
}
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
10.07.2014, 15:27     Метод поиска по массиву уникальных чисел за один проход #7
CheshireCat, мне кажется это работает только тогда, когда все числа, кроме одного встречаются четное количество раз и одно число - нечетное число раз, не?
ffgg
0 / 0 / 0
Регистрация: 10.07.2014
Сообщений: 3
10.07.2014, 15:33  [ТС]     Метод поиска по массиву уникальных чисел за один проход #8
CheshireCat, круто!
Спасибо, под конкретный случай прекрасно работает.

Цитата Сообщение от SlavaSSU Посмотреть сообщение
мне кажется это работает только тогда, когда все числа, кроме одного встречаются четное количество раз и одно число - нечетное число раз, не?
Так и есть. Что-то я не уверен, что можно сделать более универсальный способ за 1 проход...
CheshireCat
Эксперт С++
2907 / 1235 / 78
Регистрация: 27.05.2008
Сообщений: 3,307
10.07.2014, 15:37     Метод поиска по массиву уникальных чисел за один проход #9
SlavaSSU, разумеется, у данного кода есть такие ограничения. Но - мне кажется, что это задачка "на сообразительность", типа из собеседований..... и вот для данного конкретного случая - работает.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2014, 15:45     Метод поиска по массиву уникальных чисел за один проход
Еще ссылки по теме:

Функция которая переворачивает список за один проход C++
Реверс элементов в односвязанном списке за один проход C++
C++ Как считывать только одно число типа double за один проход

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

Или воспользуйтесь поиском по форуму:
SlavaSSU
213 / 158 / 44
Регистрация: 17.07.2012
Сообщений: 580
10.07.2014, 15:45     Метод поиска по массиву уникальных чисел за один проход #10
ffgg, ffgg, у тебя не было сказано, что все числа встречаются по 2 раза и одно число только один раз, поэтому подумал, что это неправильно. А вообще точно есть решение(ноя его не знаю) для такой задачи. (Даны числа, каждое число в нем повторяется k раз (k > 1 и оно неизвестно), но одно число встречается иеньше k раз, но хотя бы один раз. Найти это число. Так же надо за 1 проход и беез доп памяти) Там тоже чет с битами надо делать
Yandex
Объявления
10.07.2014, 15:45     Метод поиска по массиву уникальных чисел за один проход
Ответ Создать тему
Опции темы

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