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

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

Войти
Регистрация
Восстановить пароль
 
KostyaKulakov
Заблокирован
#1

Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. - C++

21.02.2013, 18:22. Просмотров 626. Ответов 7
Метки нет (Все метки)

сижу мучаюсь 30 минут, не как не могу составить алгоритм работы программы, подумывал нахождения через пары, но это очень долго..

вот задание:

Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме
одного. Найдите его за линейное время.

 Комментарий модератора 
Название темы должно отражать ее суть (хотя бы кратко о том, что внутри)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.02.2013, 18:22     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время.
Посмотрите здесь:
Запишите функцию для вычисления произведения целых чисел из диапазона от а до в. найдите произведение чисел, диапазон ввести с клавиатуры. В С++ C++
C++ Дана последовательность целых чисел a1, a2, ..., an. Выяснить, какое число встречается раньше - положительное или отрицательное.
C++ Дано произвольный одномерный массив целых чисел М и натуральное число n. Определить, если такие есть, количество чисел n в массиве М и их индексы
Указать диапазон, в котором находится число C++
Подсчитать,сколько раз каждое число встречается в файле C++
C++ Функция: вернуть вектор, в котором есть все числа из исходного вектора v, кроме заданного x
C++ В последовательности целых положительных чисел определить максимальное четное число и его порядковый номер.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xtorne21st
интересующийся
303 / 274 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
21.02.2013, 18:37     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #2
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
сижу мучаюсь 30 минут, не как не могу составить алгоритм работы программы, подумывал нахождения через пары, но это очень долго..
вот задание:
Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме
одного. Найдите его за линейное время.
Всё оч просто. Заносите числа в массив, сортируешь, и находишь единственные(ое) значение. Данный метод подходит не только для пары чисел, но и для любого повторяющегося значения (два или больше). Вот пример работы нахождения одинаковых элементов, переделать под ваше задания не составит труда: Одинаковые элементы массива
KostyaKulakov
Заблокирован
21.02.2013, 18:59  [ТС]     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #3
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm> // for sort
 
int one_numb_in_massiv(int* massiv, size_t size);
 
int main()
{
    const size_t size = 9;
    int arr[size] = {1,2,3,2,5,4,5,4,1};
 
    std::sort(arr, arr + size);
 
    std::cout << one_numb_in_massiv(arr, size) << std::endl;
 
    return 0;
}
 
int one_numb_in_massiv(int* massiv, size_t size)
{
    std::sort(massiv, massiv + size);
 
    for (int i = 0; i < size; ++i)
    {
        if(massiv[i] != massiv[i+1])
            return massiv[i];
        else
            ++i;
    }
 
    return 0;
 
}
Kastaneda
Форумчанин
Эксперт С++
4514 / 2856 / 228
Регистрация: 12.12.2009
Сообщений: 7,249
Записей в блоге: 1
Завершенные тесты: 1
21.02.2013, 19:04     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #4
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
C++
1
2
3
for (int i = 0; i < size; ++i)
{
    if(massiv[i] != massiv[i+1])
если все числа будут парные, то на последеней итерации будет выход за пределы массива.
И зачем сортировка дважды?
KostyaKulakov
Заблокирован
21.02.2013, 19:19  [ТС]     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #5
Цитата Сообщение от Kastaneda Посмотреть сообщение
если все числа будут парные, то на последеней итерации будет выход за пределы массива.
И зачем сортировка дважды?
хм. насчёт двойной сортировки, моя не внимательность.

насчёт выхода за приделы массива, нужно подумать.

Добавлено через 3 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
 
int one_numb_in_massiv(int* massiv, size_t size);
 
int main()
{
    const size_t size = 9;
    int arr[size] = {1,2,3,2,5,4,5,4,1};
 
    std::cout << one_numb_in_massiv(arr, size) << std::endl;
 
    return 0;
}
 
int one_numb_in_massiv(int* massiv, size_t size)
{
    std::sort(massiv, massiv + size);
 
    if((size % 2) == 0)
        return 0;
 
    for (int i = 0; i < size; ++i)
    {
        if(massiv[i] != massiv[i+1])
            return massiv[i];
        else
            ++i;
    }
 
    return 0;
 
}
ya_noob
_
201 / 145 / 9
Регистрация: 08.10.2011
Сообщений: 432
21.02.2013, 19:47     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #6
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
Найдите его за линейное время.
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
std::sort(massiv, massiv + size);
быстрая сортировка работает не за линейное время

Добавлено через 3 минуты
если диапазон чисел небольшой, то за линейное время можно выполнить поиск с помощью распределяющего подсчета
Байт
Эксперт C
15841 / 10168 / 1522
Регистрация: 24.12.2010
Сообщений: 19,171
21.02.2013, 20:37     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #7
KostyaKulakov, Если диапазон не слишком велик, можно завести char *s размером в диапазон, обнулить его, а далее как-то так
C
1
2
3
 n - очередное число
if (s[n] == 2) continue;
else s[n] ++;
Потом просматриваете s, и как только встретите 1 - вот оно!
Требуемую память для массива s можно сократить в 4 раза, упаковывая 4 двухбитных значения в один байт.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2013, 21:15     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время.
Еще ссылки по теме:
C++ Дан массив целых чисел. Выяснить верно ли, что сумма элементов массива есть четное число
C++ Дан массив целых чисел. Верно ли, что сумма квадратов элементов массива есть пятизначное число
C++ Перепись населения (Найдите, какой возраст встречается чаще всего и выведите его.)
C++ Найти слово, один и тот же символ в котором встречается максимальное число раз
Задана функция y=2x²+78x-33 Написать диапазон целых чисел от -4 до 8 C++

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

Или воспользуйтесь поиском по форуму:
diagon
Higher
1928 / 1194 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
21.02.2013, 21:15     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. #8
C++
1
2
for (int i = 0; i < arr.size(); ++i)
    answer ^= arr[i];
Yandex
Объявления
21.02.2013, 21:15     Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время.
Ответ Создать тему
Опции темы

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