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

Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 57, средняя оценка - 4.72
bubajiex
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 7
03.10.2011, 20:00     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #1
Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.10.2011, 20:00     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Посмотрите здесь:

Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы C++
C++ Максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти максимальное число из, встречающихся в матрице более одного раза C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 11:48     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #21
Цитата Сообщение от romex Посмотреть сообщение
Deviaphan, Что-то не могу придумать алгоритм с линейной сложностью + доп память. Приведите пожалуйста!
Если памяти ОЧЕНЬ много, то это просто с помощью сортировки подсчетом, которая как раз и имеет линейную сложность.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:50     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #22
Цитата Сообщение от romex Посмотреть сообщение
Что-то не могу придумать алгоритм с линейной сложностью + доп память.
Для чисел в диапазоне [0-255]
C++
1
2
3
4
5
6
7
8
9
10
11
12
int count[256] = {0};
//массив a[100]
for( int i = 0; i < 100; ++i )
   cout[ a[i] ]++;
 
int maxValue = -1;
for(int i = 255; i >=0; --i)
    if( count[i] > 1 )
    {
         maxValue = i;
         break;
    }
Соответственно, для отрицательных чисел нужно делать корректировку. И объём дополнительной памяти равен разрядности искомых чисел. В данном случае 8 бит.
romex
 Аватар для romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:56     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #23
А для вещественных чисел?

Добавлено через 1 минуту
Все, до меня дошло, спасибо...
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 11:57     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #24
Цитата Сообщение от romex Посмотреть сообщение
А для вещественных чисел?
Закодировать их с помощью биекции целыми числами, поэтому и говорю о БОЛЬШОЙ памяти. Если диапазона целых чисел не хватит, то использовать n-мерные кольца вычетов (вернее, модули) и поразрядную сортировку.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:58     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #25
Цитата Сообщение от romex Посмотреть сообщение
А для вещественных чисел?
C++
1
2
3
float f;
int count[0xFFFFFFFF] = {0};
count[*(UINT*)(&f)]++;

Шутка юмора
romex
 Аватар для romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:59     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #26
В этом случае дополнительная память конечно превышает размер исх данных, но не на много...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:59     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #27
Но возникнут проблемы с погрешностью.(
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:01     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #28
Цитата Сообщение от Deviaphan Посмотреть сообщение
Но возникнут проблемы с погрешностью.(
Разбить на целые и дробные части, а далее поразрядная сортировка.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
04.10.2011, 12:02     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #29
Цитата Сообщение от Thinker Посмотреть сообщение
Если памяти ОЧЕНЬ много, то это просто с помощью сортировки подсчетом, которая как раз и имеет линейную сложность.
Ну да, но такая сортировка подойдет только для типов, имеющих граничный диапазон. Применимость алгоритма довольно узкая.
Цитата Сообщение от Thinker Посмотреть сообщение
а далее поразрядная сортировка.
Тоже неудобно, количество разрядов в дробной части может быть велико и одинаково почти для всех чисел. Если числа случайны, вероятность повышается.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:04     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #30
Цитата Сообщение от fasked Посмотреть сообщение
Ну да, но такая сортировка подойдет только для типов, имеющих граничный диапазон. Применимость алгоритма довольно узкая.
Ну о безграничных типах мы не говорим.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 12:04     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #31
Цитата Сообщение от Thinker Посмотреть сообщение
Разбить на целые и дробные части, а далее поразрядная сортировка.
Не факт, что 3,14 == 3,14. Или что 3,14 != 3,15. Но цифры другие, разумеется, это я для примера написал. Т.е. на "равно" же вещественные не сравниваются напрямую, поэтому при подсчёте количества те же проблемы могут возникнуть. С сортировкой эта проблема решается добавлением компаратора, а вот подсчётом...
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:05     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #32
Цитата Сообщение от fasked Посмотреть сообщение
Тоже неудобно, количество разрядов в дробной части может быть велико и одинаково почти для всех чисел. Если числа случайны, вероятность повышается.
Поэтому и говорил, что если у нас памяти ОЧЕНЬ много, то такой вариант, а иначе это не пройдет
romex
 Аватар для romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 12:05     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #33
а далее поразрядная сортировка.
сложность которой NlogN, кстати...
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:07     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #34
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не факт, что 3,14 == 3,14. Или что 3,14 != 3,15. Но цифры другие, разумеется, это я для примера написал. Т.е. на "равно" же вещественные не сравниваются напрямую, поэтому при подсчёте количества те же проблемы могут возникнуть. С сортировкой эта проблема решается добавлением компаратора, а вот подсчётом...
Сравнивать нужно отдельно целые и дробные части, поэтому поразрядная сортировка.

Добавлено через 24 секунды
Цитата Сообщение от romex Посмотреть сообщение
сложность которой NlogN, кстати...
она линейная на базе сортировки подсчетом.
odip
Эксперт C++
 Аватар для odip
7224 / 3286 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
04.10.2011, 12:10     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #35
поэтому поразрядная сортировка
В этой таблице n — это количество записей, которые необходимо упорядочить, а k — это количество уникальных ключей.
...
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
...
http://ru.wikipedia.org/wiki/Алгоритм_сортировки

Надеюсь вопрос о сложности поразрядной сортировки исчерпан ?
romex
 Аватар для romex
44 / 44 / 4
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 12:11     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #36

Не по теме:

Тривиальнейшая задачка вылезла в такой ужас...



Добавлено через 1 минуту
k — это количество уникальных ключей.
тоесть два в данном случае? Только не бейте...
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:12     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #37
Цитата Сообщение от odip Посмотреть сообщение
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
Правильно, при фиксированном k - сложность линейная относительно n.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.10.2011, 14:59     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #38
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Не претендую на приз "Алгоритм года", сделал реализацию при условии, что массив нельзя изменять
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
36
37
38
39
40
41
42
43
44
45
46
47
#include <stdio.h>
#include <limits.h>
    
int * allmost_top(const int * arr, size_t size, int absTop){
    const int * ret;
    
    while ( *arr >= absTop && size > 0 ){
        ++arr;
        --size;
    }
    if ( ! size )
        return NULL;
    
    ret = arr;
    while ( --size )
        if ( *(++arr) < absTop && *ret < *arr )
            ret = arr;
    
    return (int*) ret;
}
 
int * find_same(const int * arr, size_t size, int value){
    while ( size-- ){
        if ( *arr == value )
            return (int*)arr;
        ++arr;
    }
    
    return NULL;
}
 
#define SIZE 10
int main(void){
    int arr[SIZE] = { 9, 8, 7, 2, 5, 3, 3, 4, 5, 1 };
    int * found;
    
    for ( found = allmost_top(arr, SIZE, INT_MAX); found; found = allmost_top(arr, SIZE, *found) )
        if ( find_same(found + 1, SIZE + arr - found - 1, *found) )
            break;
    
    if ( ! found )
        printf("No doubling elements in array!\n");
    else
        printf("The biggest element repeating in array have value of %d\n", *found);
    
    return 0;
}
Понятия не имею, что там со сложностью. Кстати, Thinker, буду признателен, если хорошую на ваш взгляд литературу подскажете...
Ну и очевидное ограничение - значения массива должны быть меньше INT_MAX, что, в прочем, можно исправить...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 15:06     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #39
Цитата Сообщение от easybudda Посмотреть сообщение
Понятия не имею, что там со сложностью
Не вдавался в размерности, но похоже, что для каждого элемента происходит два линейных поиска (find_some и allmost_top), так что сложность на кубическую похожа. Но я не сильно алгоритм смотрел, скорее всего квадратичная всё-таки.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.10.2011, 15:13     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Еще ссылки по теме:

Максимальное из чисел встречающихся в заданной матрице более одного раза C++
C++ Определить максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти максимальное из чисел встречающихся в массиве более одного раза C++

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

Или воспользуйтесь поиском по форуму:
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9371 / 5421 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
04.10.2011, 15:13     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза #40
Цитата Сообщение от Deviaphan Посмотреть сообщение
Но я не сильно алгоритм смотрел
Цитата Сообщение от easybudda Посмотреть сообщение
int * allmost_top(const int * arr, size_t size, int absTop)
Возвращает указатель на максимальный, но меньше, чем absTop элемент массива, или NULL, если все элементы больше или равны absTop.
Цитата Сообщение от easybudda Посмотреть сообщение
int * find_same(const int * arr, size_t size, int value)
ищет элемент со значением value в массиве после найденного "почти максимального"
В самом лучшем случае
9, 9, 8, 7, 6...
понадобится один проход по массиву и следующим же шагом всё закончится. Что, разумеется, не служит показателем "замечательности" алгоритма.
Yandex
Объявления
04.10.2011, 15:13     Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
Ответ Создать тему
Опции темы

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