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

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

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

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

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

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

вот задание:

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

 Комментарий модератора 
Название темы должно отражать ее суть (хотя бы кратко о том, что внутри)
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.02.2013, 18:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме одного. Найдите его за линейное время. (C++):

Запишите функцию для вычисления произведения целых чисел из диапазона от а до в. найдите произведение чисел, диапазон ввести с клавиатуры. В С++ - C++
Запишите функцию для вычисления произведения целых чисел из диапазона от а до в. найдите произведение чисел, диапазон ввести с клавиатуры....

Задан файл целых чисел. Указать диапазон, в котором находятся его элементы - Java SE
Задан файл целых чисел. Указать диапазон, в котором находятся его элементы. С файлом все понял, открываю, могу вывести элементы, но на...

В массиве целых чисел подсчитать сколько раз встречается каждое число - Turbo Pascal
Здравствуйте всем задача такая: В массиве целых чисел подсчитать сколько раз встречается каждое число Program Generator; Uses Crt; ...

Текстовый файл содержит несколько целых чисел. Преобразовать каждое число так, чтобы его цифры располагались в порядке убывания. - Turbo Pascal
Текстовый файл содержит несколько целых чисел. Преобразовать каждое число так, чтобы его цифры располагались в порядке убывания. Вывести в...

Количество различных чисел, каждое из которых встречается в матрице более одного раза - Delphi
ребят помогите задание не получается. Сформировать случайным образом матрицу размерности 5х4 . Подсчитать количество одинаковых чисел ...

В списке целых чисел удалить из каждой группы подряд идущих одинаковых элементов все, кроме одного - Turbo Pascal
Здравствуйте, Вы не могли бы помочь с задачей контрольной работы? "Составить программу. В списке целых чисел удалить из каждой...

7
xtorne21st
интересующийся
304 / 275 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
21.02.2013, 18:37 #2
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
сижу мучаюсь 30 минут, не как не могу составить алгоритм работы программы, подумывал нахождения через пары, но это очень долго..
вот задание:
Есть диапазон целых чисел, в котором каждое число встречается дважды, кроме
одного. Найдите его за линейное время.
Всё оч просто. Заносите числа в массив, сортируешь, и находишь единственные(ое) значение. Данный метод подходит не только для пары чисел, но и для любого повторяющегося значения (два или больше). Вот пример работы нахождения одинаковых элементов, переделать под ваше задания не составит труда: Одинаковые элементы массива
1
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;
 
}
0
Kastaneda
Jesus loves me
Эксперт С++
4729 / 2933 / 242
Регистрация: 12.12.2009
Сообщений: 7,442
Записей в блоге: 2
Завершенные тесты: 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])
если все числа будут парные, то на последеней итерации будет выход за пределы массива.
И зачем сортировка дважды?
0
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;
 
}
0
ya_noob
_
313 / 147 / 9
Регистрация: 08.10.2011
Сообщений: 432
21.02.2013, 19:47 #6
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
Найдите его за линейное время.
Цитата Сообщение от KostyaKulakov Посмотреть сообщение
std::sort(massiv, massiv + size);
быстрая сортировка работает не за линейное время

Добавлено через 3 минуты
если диапазон чисел небольшой, то за линейное время можно выполнить поиск с помощью распределяющего подсчета
0
Байт
Диссидент
Эксперт C
17227 / 11297 / 1789
Регистрация: 24.12.2010
Сообщений: 22,241
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 двухбитных значения в один байт.
0
diagon
Higher
1933 / 1199 / 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];
3
21.02.2013, 21:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.02.2013, 21:15
Привет! Вот еще темы с ответами:

Последовательность вводится N целых чисел. Найдите минимальное и максимальное число из введенных чисел - Pascal ABC
Последовательность вводится N целых чисел. Найдите минимальное и максимальное число из введенных чисел.

Определить, встречается ли число 7 в массиве целых чисел - C (СИ)
Напишите программу, которая дает ответ &quot;да&quot; или &quot;нет&quot;, в зависимости от того, встречается ли число 7 у массиве целых...

Дан массив целых чисел. Определить все уникальные числа в массиве и сколько раз каждое из них встречается в массиве. - C++
Написать программу для решения следующей задачи. Дан массив целых чисел. Определить все уникальные числа в массиве и сколько раз каждое из...

Из 3 натуральных чисел выбрать число в котором заданная цифра встречается максимальное количество раз - Pascal ABC
Помогите написать программу с помощью процедуры. Из 3 натуральных чисел выбрать число в котором заданная цифра встречается максимальное...


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

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

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