0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 7

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

03.10.2011, 20:00. Показов 12706. Ответов 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
Ответ Создать тему
Опции темы

Новые блоги и статьи
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
Оттачиваю умение писать js программы.
russiannick 30.08.2026
Проектом выходного дня стало написание Книги шифров Виженера. Итогом стала версия 200, синий туман. Синий туман назван так, потому что замораживает текст под собой. Нажатие синих кнопок управляют. . .
мат медиц модель 30. презентация проекта
anaschu 27.08.2026
хоп хоп хоп хидахоп, а я кладую))
Как у меня протекала болезнь
zorxor 27.08.2026
Здравствуйте, друзья! Эта запись блога предназначена именно для вас - для моих дорогих друзей, которые знали меня лично. Чтобы ответить на вопрос - а что же со мной произошло на самом деле? Я учился. . .
Нашел вот забавное видео о измерениях. Лучшее что я видел на эту тему
kumehtar 26.08.2026
ILETXiw9bMQ Основная суть и тезисы по измерениям: 0D (Нулевое измерение): точка, не имеющая длины, ширины, высоты или объема. Объект не может перемещаться в 0D. 1D (Первое измерение):. . .
[EasyBuilder Pro] Памятка по разработке для панелей Weintek
ФедосеевПавел 26.08.2026
Памятка по разработке для панелей Weintek ВВЕДЕНИЕ Ранее, при реализации проектов основное внимание уделял разработке управляющей программы для контроллера, а панели оператора доставалось время. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru