0 / 0 / 0
Регистрация: 03.10.2011
Сообщений: 7
|
|
1 | |
Найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза03.10.2011, 20:00. Показов 11477. Ответов 46
Метки нет (Все метки)
Помогите пожалуйста
задачка вроде простенькая : найти максимальное из чисел встречающихся в данном одномерном массиве более одного раза
0
|
03.10.2011, 20:00 | |
Ответы с готовыми решениями:
46
Найти максимальное из чисел встречающихся в массиве более одного раза Найти максимальное из чисел, встречающихся в заданной матрице более одного раза Двумерный массив. Найти: максимальное из чисел, встречающихся в заданной матрице более одного раза Найти максимальное из чисел встречающихся в матрице более одного раза. Сделать используя указатели и классы |
03.10.2011, 20:21 | 2 |
Код
1) Присваиваете переменной max минимальное значение для ее типа. 2) Пробегаете двойным циклом по массиву. 3) if(arr[i] == arr[j]) { if(arr[i] > max) max = arr[i] break;//переходите на следующую итерацию цикла i } 4) После циклов ставите условие на max, если max == минимальному значению для типа переменной max, то все числа входят в массив только единожды, иначе выводите max По хорошему надо вообще переменную bool, чтобы отслеживать изменения max, поскольку если в массиве будут только элементы, равные минимальному допустимому значению для типа max, тогда программа выдаст, что максимальных повторяющихся элементов нет. Добавлено через 3 минуты Не по теме: Запомните, а лучше запишите. Плодить темы на форуме "не есть хорошо"
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
03.10.2011, 20:41 | 3 |
1
|
soon
|
03.10.2011, 21:01
#4
|
Не по теме: Мда. Что-то о сортировке я даже и не подумал. :scratch:
0
|
03.10.2011, 23:25 | 5 |
Для произвольного случая сложность будет O(n*log n). Интересно, а еще оптимальнее можно.
Добавлено через 22 минуты Нет, нельзя, сложность данной задачи эквивалентна сложности сортировки
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
04.10.2011, 06:35 | 6 |
0
|
04.10.2011, 08:44 | 7 |
Нельзя, задача эквивалентна сортировке, хоть можно и без нее обойтись, но сложность алгоритма та же будет. Контейнер тоже нельзя, а то просто будет слишком. Имеется ввиду написать алгоритм без использования дополнительной памяти, работать только с массивом.
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
04.10.2011, 09:00 | 8 |
В задании такого ограничения не указывается.)
Хотя, я не учёл сложность поиска значения в мапе. Т.е. всё равно близко к N*logN получается. С сортировкой самый простой вариант.
0
|
04.10.2011, 09:08 | 9 |
Почти да. Если же элементы массива нельзя менять местами, то алгоритм поиска будет похож на сортировку.
Добавлено через 1 минуту Просто задался сам для себя таким вопросом
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
04.10.2011, 09:15 | 10 |
Что-то я туплю вообще. За один проход решается задача, с использованием трёх дополнительных переменных.Одна для текущего максимального повторённого значения, одна для счётчика и одна для текущего максимального не повторённого значения.
Так что всё предельно просто.) Добавлено через 53 секунды Если количество повторений не важно, то и счётчик можно не использовать.
0
|
Заблокирован
|
||||||
04.10.2011, 09:26 | 11 | |||||
- ниже С++ реализация твоего алгоритма(никаких контейнеров, сортировок, макс элемент выбираем ещё при вводе)
1
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
04.10.2011, 09:32 | 13 |
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
04.10.2011, 09:49 | 15 |
Алгоритм очень немного не корректен. Минимальное значение int != -INT_MAX. Т.е. существует вариант заполнения массива, при котором алгоритм вернёт не правильное значение.
Добавлено через 13 минут Я подумал получше и понял, что не прав. Не работает такой алгоритм.)
0
|
Делаю внезапно и красиво
1313 / 1228 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
|
|
04.10.2011, 10:03 | 17 |
Я придумал работающий (на этот раз) алгоритм, но требуется дополнительная память. Причём ОЧЕНЬ много её требуется, в соответствии с разрядностью чисел. Зато, линейная сложность.
0
|
45 / 45 / 9
Регистрация: 11.04.2010
Сообщений: 223
|
|
04.10.2011, 11:45 | 20 |
Deviaphan, Что-то не могу придумать алгоритм с линейной сложностью + доп память. Приведите пожалуйста!
0
|
04.10.2011, 11:45 | |
04.10.2011, 11:45 | |
Помогаю со студенческими работами здесь
20
Найти максимальное из чисел, встречающихся в заданном двумерном массиве более одного раза Обменять максимальное и минимальное из чисел, встречающихся в массиве более одного раза Найти максимальное из чисел, встречающихся в матрице более одного раза Найти максимальное из чисел встречающихся в матрице более одного раза Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |