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

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

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

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

10.07.2014, 14:28. Просмотров 426. Ответов 9
Метки нет (Все метки)

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

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

Проход по массиву - C++
Всем здравствуйте, что то я сейчас затормозил. В общем суть задачки проста найти из данного массива (действительных чисел) первое число...

Проход по массиву и удаление одинаковых слов - C++
Доброе утро!Программа выполняет чтение вводимых слов с консоли и записывает каждое слово в массив по нажатию enter, чтение с консоли...

За единственный проход по массиву найти неповторяющийся элемент - C++
здравствуйте, уважаемые программисты.) у меня такой вопросик: дан массив из нечетного кол-ва элементов, каждый из который встречается в...

Сортировка массива за один проход - C++
Помогите. Нужно отсортировать массив так, чтобы справа были отрицательные, слева положительные и нули посередине. При этом (!) нужно...

Сортировка в один проход по нескольким полям - C++
Добрый вечер, #include <iostream> #include <ctime> #include <vector> #include <algorithm> using namespace std; class...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Kukurudza
105 / 86 / 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
35 / 35 / 16
Регистрация: 30.10.2013
Сообщений: 211
10.07.2014, 14:54 #4
А если сначала загнать весь массив в строку и брать каждый элемент массива и с помощью strrchr возвращать индекс последнего вхождения символа и индекс первого вхождения strchr, сравнивать с индексом в массиве? Так не покатит?
Kukurudza
105 / 86 / 6
Регистрация: 29.08.2012
Сообщений: 539
10.07.2014, 14:59 #5
это О(n2)
CheshireCat
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,368
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
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
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
Эксперт С++
2892 / 1241 / 78
Регистрация: 27.05.2008
Сообщений: 3,368
10.07.2014, 15:37 #9
SlavaSSU, разумеется, у данного кода есть такие ограничения. Но - мне кажется, что это задачка "на сообразительность", типа из собеседований..... и вот для данного конкретного случая - работает.
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
10.07.2014, 15:45 #10
ffgg, ffgg, у тебя не было сказано, что все числа встречаются по 2 раза и одно число только один раз, поэтому подумал, что это неправильно. А вообще точно есть решение(ноя его не знаю) для такой задачи. (Даны числа, каждое число в нем повторяется k раз (k > 1 и оно неизвестно), но одно число встречается иеньше k раз, но хотя бы один раз. Найти это число. Так же надо за 1 проход и беез доп памяти) Там тоже чет с битами надо делать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.07.2014, 15:45
Привет! Вот еще темы с ответами:

Реверс элементов в односвязанном списке за один проход - C++
Добрый день! Есть структура, представляющая из себя односвязный список. Как можно изменить порядок элементов на обратный в этом списке за...

Функция которая переворачивает список за один проход - C++
Написала функцию. Эта функция переворачивает список за один проход. Создаю новый список и в него поочередно записываю элементы,но в другом...

Найти все бракованные изделия на конвейере за один проход робота-контролера - C++
Всем добрый вечер! Вот попалась такая задача: на конвейере по производству телефонов работает робот-контролер. Он идет вдоль конвейера...

Как считывать только одно число типа double за один проход - C++
Теперь измените тело цикла так, чтобы он считывал только одно число типа double за один проход. Определите две переменные, чтобы...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.07.2014, 15:45
Ответ Создать тему
Опции темы

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