Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.53/58: Рейтинг темы: голосов - 58, средняя оценка - 4.53
0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 7

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

03.10.2011, 20:00. Показов 13138. Ответов 46
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Помогите пожалуйста
задачка вроде простенькая :
найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
0
Лучшие ответы (1)
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
03.10.2011, 20:00
Ответы с готовыми решениями:

Найти максимальное из чисел встречающихся в массиве более одного раза
Найти максимальное из чисел, встречающихся в данном одномерном массиве более одного раза. Вывести количество посторов этого числа.

Найти максимальное из чисел, встречающихся в заданной матрице более одного раза
дана целочисленная прямоугольная матрица определить: максимальное из чисел встречающихся в заданной матрице более одного раза ...

Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза
Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза Матрица: 2 4 7 6 5 8 9 34 43 4 34 53 45 345 3 6 5 56...

46
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 11:48
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от romex Посмотреть сообщение
Deviaphan, Что-то не могу придумать алгоритм с линейной сложностью + доп память. Приведите пожалуйста!
Если памяти ОЧЕНЬ много, то это просто с помощью сортировки подсчетом, которая как раз и имеет линейную сложность.
1
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:50
Цитата Сообщение от 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 бит.
1
 Аватар для romex
45 / 45 / 9
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:56
А для вещественных чисел?

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

Шутка юмора
0
 Аватар для romex
45 / 45 / 9
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 11:59
В этом случае дополнительная память конечно превышает размер исх данных, но не на много...
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 11:59
Но возникнут проблемы с погрешностью.(
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:01
Цитата Сообщение от Deviaphan Посмотреть сообщение
Но возникнут проблемы с погрешностью.(
Разбить на целые и дробные части, а далее поразрядная сортировка.
0
Эксперт С++
 Аватар для fasked
5045 / 2624 / 241
Регистрация: 07.10.2009
Сообщений: 4,310
Записей в блоге: 5
04.10.2011, 12:02
Цитата Сообщение от Thinker Посмотреть сообщение
Если памяти ОЧЕНЬ много, то это просто с помощью сортировки подсчетом, которая как раз и имеет линейную сложность.
Ну да, но такая сортировка подойдет только для типов, имеющих граничный диапазон. Применимость алгоритма довольно узкая.
Цитата Сообщение от Thinker Посмотреть сообщение
а далее поразрядная сортировка.
Тоже неудобно, количество разрядов в дробной части может быть велико и одинаково почти для всех чисел. Если числа случайны, вероятность повышается.
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:04
Цитата Сообщение от fasked Посмотреть сообщение
Ну да, но такая сортировка подойдет только для типов, имеющих граничный диапазон. Применимость алгоритма довольно узкая.
Ну о безграничных типах мы не говорим.
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 12:04
Цитата Сообщение от Thinker Посмотреть сообщение
Разбить на целые и дробные части, а далее поразрядная сортировка.
Не факт, что 3,14 == 3,14. Или что 3,14 != 3,15. Но цифры другие, разумеется, это я для примера написал. Т.е. на "равно" же вещественные не сравниваются напрямую, поэтому при подсчёте количества те же проблемы могут возникнуть. С сортировкой эта проблема решается добавлением компаратора, а вот подсчётом...
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:05
Цитата Сообщение от fasked Посмотреть сообщение
Тоже неудобно, количество разрядов в дробной части может быть велико и одинаково почти для всех чисел. Если числа случайны, вероятность повышается.
Поэтому и говорил, что если у нас памяти ОЧЕНЬ много, то такой вариант, а иначе это не пройдет
0
 Аватар для romex
45 / 45 / 9
Регистрация: 11.04.2010
Сообщений: 223
04.10.2011, 12:05
а далее поразрядная сортировка.
сложность которой NlogN, кстати...
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:07
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не факт, что 3,14 == 3,14. Или что 3,14 != 3,15. Но цифры другие, разумеется, это я для примера написал. Т.е. на "равно" же вещественные не сравниваются напрямую, поэтому при подсчёте количества те же проблемы могут возникнуть. С сортировкой эта проблема решается добавлением компаратора, а вот подсчётом...
Сравнивать нужно отдельно целые и дробные части, поэтому поразрядная сортировка.

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

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

Не по теме:

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



Добавлено через 1 минуту
k — это количество уникальных ключей.
тоесть два в данном случае? Только не бейте...
0
Эксперт С++
 Аватар для Thinker
4267 / 2241 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
04.10.2011, 12:12
Цитата Сообщение от odip Посмотреть сообщение
Поразрядная сортировка — Сложность алгоритма: O(n·k); требуется O(k) дополнительной памяти.
Правильно, при фиксированном k - сложность линейная относительно n.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12848 / 7597 / 1766
Регистрация: 25.07.2009
Сообщений: 13,985
04.10.2011, 14:59
Лучший ответ Сообщение было отмечено Памирыч как решение

Решение

Не претендую на приз "Алгоритм года", сделал реализацию при условии, что массив нельзя изменять
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, что, в прочем, можно исправить...
0
Делаю внезапно и красиво
Эксперт С++
 Аватар для Deviaphan
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
04.10.2011, 15:06
Цитата Сообщение от easybudda Посмотреть сообщение
Понятия не имею, что там со сложностью
Не вдавался в размерности, но похоже, что для каждого элемента происходит два линейных поиска (find_some и allmost_top), так что сложность на кубическую похожа. Но я не сильно алгоритм смотрел, скорее всего квадратичная всё-таки.
0
Модератор
Эксперт PythonЭксперт JavaЭксперт CЭксперт С++
 Аватар для easybudda
12848 / 7597 / 1766
Регистрация: 25.07.2009
Сообщений: 13,985
04.10.2011, 15:13
Цитата Сообщение от 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...
понадобится один проход по массиву и следующим же шагом всё закончится. Что, разумеется, не служит показателем "замечательности" алгоритма.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
04.10.2011, 15:13

Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы
Ребята..помогите,пожалуйста.Надо решить задачу,а никак не выходит(даже не знаю..прочитала в книге все про указатели и не пойму как...

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

Обменять максимальное и минимальное из чисел, встречающихся в массиве более одного раза
Здравствуйте! Помогите, пожалуйста с программой: Найти максимальное и минимальное из чисел, встречающихся в целочисленном массиве...

Найти максимальное из чисел, встречающихся в матрице более одного раза
Дана действительная матрица размерности (n n × ). Найти максимальное из чисел, встречающихся в матрице более одного раза.

Найти максимальное из чисел встречающихся в матрице более одного раза
оформить в ввиде процедуры.


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

Или воспользуйтесь поиском по форуму:
40
Ответ Создать тему
Новые блоги и статьи
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем
yariko 12.11.2026
Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .
Транслитерация текста с кириллицы на латиницу (вариант №1)
Maks 11.11.2026
Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта
8Observer8 08.11.2026
Содержание блога | English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle | Объем: 768 стр. Ссылки: Amazon . . .
Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят
zorxor 08.11.2026
Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .
Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ.
zorxor 08.11.2026
Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .
Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL
8Observer8 07.11.2026
Содержание блога | English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике
Maks 07.11.2026
Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru