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

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

03.10.2011, 20:00. Показов 12655. Ответов 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
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
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
12843 / 7592 / 1766
Регистрация: 25.07.2009
Сообщений: 13,981
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
Ответ Создать тему
Новые блоги и статьи
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .
[EasyBuilder Pro] Памятка по разработке для панелей Weintek
ФедосеевПавел 26.08.2026
Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
Модель по догадкам
anaschu 25.08.2026
Прошло две недели. Я уже рассказывал, как разговаривал с сотрудниками у сортировки и как понял, что главная ветка — не про приёмку, а про отбор. Но тогда я думал, что понял механику. На этой неделе я. . .
Запись в регистр сведений независимо от заполненности табличной части
Maks 25.08.2026
Реализация из решения ниже выполнена на нетиповом документе с несколькими табличными частями, разработанного в КА2. Задача: Обеспечить запись документа в регистр сведений независимо от. . .
Ноутбук Альфария
kumehtar 24.08.2026
Встретился тут в сети ноутбук Альфария, примарха Альфа-Легиона. Хотя возможно, это ноутбук Омегона, разумеется. Ну как вам?
Мастера простых решений
DevAlt 23.08.2026
В сишарп стэках winforms, да и wpf существует сложная система связывания источниках данных и элементов формы(текстовые поля и метки), опирается все это на технологию событий и мета. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru