Как найти второй максимум в списке из последовательности чисел?
Пожалуй эффективнее всего будет воспользоваться функцией heapq.nlargest():
from heapq import nlargest res = nlargest(2, items)[1] Отслеживать
ответ дан 6 окт 2019 в 7:14
MaxU — stand with Ukraine MaxU — stand with Ukraine
149k 12 12 золотых знаков 59 59 серебряных знаков 132 132 бронзовых знака
Можно написать функцию:
def find_maxes(array, count): # копируем список чтобы не изменить старую copied_array = array.copy() maximums = [] if count > len(copied_array): raise ValueError('Количество не может превышать длину списка') for _ in range(count): max_val = max(copied_array) # получаем максимальное значение copied_array.remove(copied_array) # удаляем его из списка maximums.append(max_val) # добавляем в наш ожидаемый результат return maximums или же можно поступить хитро
def find_maxes(array, count): if count > len(array): raise ValueError('Количество не может превышать длину списка') sorted_array = sorted(array) # отсортировать список # Забрать последние элементы из спика так как они будут максимальными return sorted_array[len(array)-count: len(array)] Как найти второй максимум с
задание найти второй максимум в матрице. Есть вот такой алгоритм:
1. находим MAX1;
2. Заменяем его на заведомо малое число;
3. Повторяем процедуру поиска.
Если я напишу вот так:
m1=0; for(int i=0;im1) > a[i][j]=0; >
Какие в этом случае обнулится максимальный элемент матрицы или в процессе поиска обнулятся все элементы матрицы, которые больше нуля?
спят подружки вредные безмятежным сном,
Снятся мышкам хлебные крошки под столом, Буратинам — досточки, кошкам — караси,
Всем собакам — косточки, программистам — Си (с)
| Arcueid1691 |
| Посмотреть профиль |
| Найти ещё сообщения от Arcueid1691 |
Меркантильный кю
Участник клуба
Регистрация: 02.02.2008
Сообщений: 1,001
Сообщение от Arcueid1691
Какие в этом случае обнулится максимальный элемент матрицы или в процессе поиска обнулятся все элементы матрицы, которые больше нуля?
Мой мозг отказывается интерпретировать эту фразу
Алгоритм намного проще:
1. max1 = A[1][1]; max2 = A[1][1];
2. Бежим по матрице.
а) если очередной элемент б) если он > max2, но < max1, то max2 = A[i][j]
в) если он >= max1, то max2 = max1; max1 = A[i][j]
Росли вроде умными, выросли дурнями. (c)А.Васильев
Пользователь
Регистрация: 18.09.2009
Сообщений: 38
Эм, по-идее это не будет компилироваться:
m1=0; for(int i=0;im1) m1 = a[i][j]; > a[i][j]=0; >
Переменная j у тебя существует только в области видимости вложенного цикла (только что проверил, Visual Studio 2005 ругается на нее в строчке
a[i][j]=0;Если объявить счетчики вне циклов, то в той же злочастной строчке:
a[i][j]=0;j будет равен y (последнее значение j, не удовлетворяющее условию). У меня в той же вижуалке он обнулил первые элементы каждой строки начиная со первой (нулевую пропустил).
И естесственно сругался «stack corrupted», т.к. на последней итерации обнуляет элемент a[2][3], что уже за пределами памяти матрицы.
А почему бы не находить сразу два максимума?
int m1=0; int m2=0; for(int i=0;i m1) < m1 = a[i][j]; >else < if(a[i][j] >m2) m2 = a[i][j]; > > >
В итоге m2 будет второй максимум. Если нужен уникальный, т.е. в последовательности:
96 47 53 12 0 96 45
второй максимум — 53, то
if (a[i][j] > m1)надо поменять на
if (a[i][j] >= m1)Как найти второй максимум с
Прошу помощи специалистов или тех кто в этом разбирается.
По причине серьёзной болезни я пропустил больше половины семестра.
Теперь надо нагонять материал. Задача такая: Найти второй максимум массива, массив вводиться с клавиатуры. Второй максимум я найти смог, а ввод с клавиатуры не получается. Помогите кто знает. Изменить именно эту программу:
Форумчанин
Регистрация: 16.09.2011
Сообщений: 114
Второй максимум — это наибольший элемент из тех, что меньше максимального? Ну типа у массива 1 5 3 8 первый максимум 8, а второй 5 ? Так что ли?
| JuniorProger |
| Посмотреть профиль |
| Найти ещё сообщения от JuniorProger |
Регистрация: 21.12.2011
Сообщений: 5
Сообщение от JuniorProger
Второй максимум — это наибольший элемент из тех, что меньше максимального? Ну типа у массива 1 5 3 8 первый максимум 8, а второй 5 ? Так что ли?
именно так
Форумчанин
Регистрация: 16.09.2011
Сообщений: 114
Ну тогда держи
#include #define MIN -1 using namespace std; int main()< int max=MIN,second_max=MIN; int arr[6]; //=; for(int i=0;i<6;i++)< cin>>arr[i]; >; for(int i=0;i<6;i++)< cout<<"::"<; for(int i=0;i<6;i++)< if(arr[i]>max) < second_max=max; max=arr[i]; >> cout>i; return 0; > А в чем проблема то была? Ты же в конце i считываешь с клавиатуры. Кстати в циклах i<6, а не i<5 Последний раз редактировалось JuniorProger; 21.12.2011 в 17:21 .
| JuniorProger |
| Посмотреть профиль |
| Найти ещё сообщения от JuniorProger |
Регистрация: 21.12.2011
Сообщений: 5
Премного благодарен, всеуважаемый JuniorProger. Побольше бы таких людей как ты.
Форумчанин
Регистрация: 16.09.2011
Сообщений: 114
А вообще всякие задачки с массивами и примеры их решения с объяснениями есть почти в каждом учебнике по С++. Наверняка в том, по которому вас учат (или в лекциях), что-то подобное есть. Хотя, иногда теоретический материал не сразу понятен и на примерах быстрее понимаешь. Спрашивай, если что, но и сам думай, читай и пытайся понять.
| JuniorProger |
| Посмотреть профиль |
| Найти ещё сообщения от JuniorProger |
| Похожие темы | ||||
| Тема | Автор | Раздел | Ответов | Последнее сообщение |
| к элементам первой половины массива добавить минимум, а к элементам второй — добавить максимум | specialist | Паскаль, Turbo Pascal, PascalABC.NET | 3 | 08.05.2011 01:46 |
| Максимум Массива | SKyzZz | Общие вопросы C/C++ | 3 | 15.02.2011 22:08 |
| с++ первый максимум | kate311893 | Помощь студентам | 0 | 26.05.2010 14:11 |
| максимум | meteor | Microsoft Office Excel | 2 | 06.12.2008 13:08 |
Как мы можем найти второй максимум из массива эффективно?
Можно ли найти второе максимальное число из массива целых чисел, пройдя массив только один раз? В качестве примера у меня есть массив из пяти целых чисел, из которых я хочу найти второе максимальное число. Вот попытка, которую я дал в интервью:
#define MIN -1 int main() < int max=MIN,second_max=MIN; int arr[6]=; for(int i=0;i <5;i++)< cout<<"::"<for(int i=0;i<5;i++)< if(arr[i]>max) < second_max=max; max=arr[i]; >> cout>i; return 0; > Интервьюер, однако, придумал тестовый пример int arr[6]=<5,4,3,2,1,0>; , который предотвращает его переход в состояние if во второй раз. Я сказал интервьюеру, что единственный способ — разобрать массив два раза (два цикла for ). У кого-нибудь есть лучшее решение?
Xinus 06 март 2010, в 15:44
Поделиться
Имеет ли значение, что массив переупорядочивается в процессе нахождения второго максимума?
Martin 06 март 2010, в 21:39
использовать структуру Heap вместо array или использовать структуру sorted array
gaussblurinc 28 авг. 2013, в 09:40
Поделиться:
16 ответов
Лучший ответ
Инициализация max и second_max до -1 неверна. Что делать, если массив имеет значения, такие как ?
Вместо этого вы должны взять первые 2 элемента массива (предположим, что массив имеет не менее 2 элементов), сравнить их, назначить меньший second_max , а более крупный — max :
if(arr[0] > arr[1]) < second_max = arr[1]; max = arr[0]; >else
Затем начните сравнение с третьим элементом и обновите max и/или second_max по мере необходимости:
for(int i = 2; i < arr_len; i++)< // use >= n not just > as max and second_max can hav same value. Ex: if(arr[i] >= max) < second_max=max; max=arr[i]; >else if(arr[i] > second_max) < second_max=arr[i]; >> codaddict 06 март 2010, в 15:36
Поделиться
Вы правы насчет отрицательных чисел. Однако ваш код будет давать second_max == max, если есть два вхождения max-числа. Правильно это или нет, неясно указано в вопросе.
Anders Abel 06 март 2010, в 14:28
Мне нравится тест для первых двух элементов до цикла for. Может даже быть защита для вырожденного случая массива из двух элементов . и полностью избежать цикла.
Stan Graves 06 март 2010, в 14:31
@Anders: Андерс: Точно. Для ввода типа <1,2,3,3>. Дефект second_max может варьироваться. Это может быть просто second_max или second_max, отличное от max. Я пошел с 1-го, поскольку это имеет смысл (по крайней мере, для меня), и это то, что будет делать даже библиотека std :: nth_element.
codaddict 06 март 2010, в 14:33
Небольшая оптимизация, вы можете сначала сравнить текущий элемент массива в цикле с second_max, а затем, если это пройдет, сравнить с max. Таким образом, это будет выглядеть так: if (arr [i]> second_max)
abhinav 06 март 2010, в 15:14
Показать ещё 2 комментария
Самое простое решение — использовать std::nth_element .
avakar 06 март 2010, в 15:59
Поделиться
Хорошо, объясните, как реализован std :: nth_element.
Svante 06 март 2010, в 15:13
avakar 06 март 2010, в 15:26
+1 Самый простой, без ошибок, оптимизированный.
Jon-Eric 06 март 2010, в 16:32
Я удалил мой ответ, так как это был в значительной степени обман.
Robert Davis 06 март 2010, в 16:53
В зависимости от того, как выбран круг, это может быть O(N^2) в худшем случае. Гарантированный O(N) алгоритм за один проход, хотя и не расширяемый, лучше для этой конкретной проблемы.
polygenelubricants 06 март 2010, в 18:57
@polygenelubricants, вы можете уточнить? Проблема O(n) в худшем случае. Страница, на которую я ссылался, предоставляет алгоритм наихудшего случая O(n) .
avakar 06 март 2010, в 20:43
Как я уже сказал, это зависит от того, как выбран стержень. Алгоритм выбора на основе разделов, как и алгоритм быстрой сортировки на основе разделов, может демонстрировать O(N^2) наихудшее поведение, если вы не выберете ось очень тщательно (wikipedia: «Как и в случае быстрой сортировки, производительность алгоритма чувствительна к выбранной точке. Если последовательно выбираются плохие точки, это ухудшает выбор, основанный на минимуме, описанный ранее, и поэтому может потребовать до O (n ^ 2) времени «). Однако на практике в среднем даже потенциально плохой алгоритм выбора сводной точки достаточно хорош.
polygenelubricants 06 март 2010, в 20:57
Я упустил тот момент, что стандарт гарантирует ожидаемую линейную сложность для std::nth_element , а не для наихудшего случая. Таким образом, реализация может действительно демонстрировать суперлинейное время выполнения.
avakar 06 март 2010, в 21:24
@Jon-Eric: Джон-Эрик: оптимизирован для общего n-го решения, а не для n = 2 .
Karoly Horvath 05 нояб. 2011, в 00:14
Это работает, когда есть дубликаты в массиве?
Brahim 04 июнь 2015, в 08:16
Показать ещё 8 комментариев
Вам потребуется второе испытание:
for(int i=0;i<5;i++)< if(arr[i]>max) < second_max=max; max=arr[i]; >else if (arr[i] > second_max && arr[i] != max) < second_max = arr[i]; >>
Anders Abel 06 март 2010, в 15:55
Поделиться
Во втором тесте убедитесь, что arr [i]! = Max; в противном случае ваши max и second_max могут оказаться одинаковыми, что может быть проблемой в зависимости от того, как вы хотите, чтобы все работало.
ty. 06 март 2010, в 14:12
Спасибо за комментарий, я обновил код.
Anders Abel 06 март 2010, в 14:19
Сбой для ввода
TopCoder 06 март 2010, в 14:27
@TopCoder: Каково правильное поведение в случае двух случаев максимального значения? Я не думаю, что это четко указано в вопросе.
Anders Abel 06 март 2010, в 14:34
Вы можете изменить первый тест на «arr [i]> = max» и удалить «arr [i]! = Max» из второго теста. Это позволило бы max и second_max равняться одному и тому же значению, но только если это значение дублируется в массиве. В зависимости от деталей вопроса, это может быть правильным ответом.
Stan Graves 06 март 2010, в 14:37
Сбой, потому что вы жестко запрограммировали 5 как длину массива.
Robert Davis 06 март 2010, в 16:42
Показать ещё 4 комментария
Ваш исходный код в порядке, вам просто нужно инициализировать переменные max и second_max. Используйте первые два элемента в массиве.
Hans Passant 06 март 2010, в 15:44
Поделиться
Здесь вы находитесь:
std::pair GetTwoBiggestNumbers(const std::vector& array) < std::pairbiggest; biggest.first = std::max(array[0], array[1]); // Biggest of the first two. biggest.second = std::min(array[0], array[1]); // Smallest of the first two. // Continue with the third. for(std::vector::const_iterator it = array.begin() + 2; it != array.end(); ++it) < if(*it >biggest.first) < biggest.second = biggest.first; biggest.first = *it; >else if(*it > biggest.second) < biggest.second = *it; >> return biggest; > Johann Gerell 06 март 2010, в 15:10
Поделиться
Это никогда не сдвигает первое место на второе. Рассмотрим <5, 1, 7>.
John Marshall 06 март 2010, в 14:41
Странное использование std :: for_each.
pmr 06 март 2010, в 14:46
@John: Джон: Спасибо — исправлено!
Johann Gerell 06 март 2010, в 15:09
@pmr: «Странное использование» — каким образом?
Johann Gerell 06 март 2010, в 15:10
@Johann: std::for_each() нельзя использовать как оператор цикла — это функция. Попробуйте скомпилировать свой код и посмотреть, как пролетят все эти ошибки. Вы , вероятно , имел в виду , чтобы написать for вместо. (примечание: даже если бы существовал оператор for_each , ++it противоречило бы намерению)
Georg Fritzsche 06 март 2010, в 15:15
@gf: Ой, дни C ++ были слишком давно . — исправлено.
Johann Gerell 06 март 2010, в 15:46
@Johann: Как сказал gf, вы используете std :: for_each неправильно. Вы даже не можете определить блок внутри оператора for как функтор, так как он зависит от значений вне его. Это всего лишь небольшой недостаток. Просто измените std :: for_each на for.
pmr 06 март 2010, в 15:48
@pmr: Спасибо — я уже изменил это. 🙂
Johann Gerell 06 март 2010, в 20:26
@Johann: я написал комментарий, а вы его редактировали. Не хотел продолжать избивать этот незначительный недостаток 🙂
pmr 06 март 2010, в 21:51
Показать ещё 7 комментариев
Проверьте это решение.
max1 = a[0]; max2 = a[1]; for (i = 1; i < n; i++) < if (max1 < a[i]) < max2 = max1; max1 = a[i]; >if (max2 == max1) max2 = a[i + 1]; if (max2 == a[n]) < printf("All numbers are the same no second max.\n"); return 0; >if (max2
mitta 16 окт. 2011, в 20:41
Поделиться
Что произойдет, если a [0] = a [1] = max? Я думаю, что есть проблема тогда
Origin 09 нояб. 2012, в 08:29
Другим способом решения этой проблемы является использование сравнений между элементами. Например,
Сравните 1,2 и скажем max = 2 и second max = 1
Теперь сравните 3 и 4 и сравните наибольшее из них с макс.
if element > max second max = max element = max else if element > second max second max = element Преимущество этого заключается в том, что вы удаляете два числа всего за два сравнения.
Сообщите мне, если у вас возникли проблемы с пониманием этого.
Boolean 07 март 2010, в 07:28
Поделиться
опечатка .. вам нужно max = элемент.
Karoly Horvath 05 нояб. 2011, в 00:17
Шаг 1. Решите первые два числа.
Шаг 2. Прокрутите оставшиеся числа. Шаг 3. Поддерживайте максимальный максимум и второй максимум. Шаг 4. При обновлении второго максимума помните, что вы не делаете максимальный и второй максимальный равным.
Протестировано для отсортированного ввода (восходящего и нисходящего), случайного ввода, ввода с дубликатами, отлично работает.
#include #define MAX 50 int GetSecondMaximum(int* data, unsigned int size) < int max, secmax; // Decide on first two numbers if (data[0] >data[1]) < max = data[0]; secmax = data[1]; >else < secmax = data[0]; max = data[1]; >// Loop through remaining numbers for (unsigned int i = 2; i < size; ++i) < if (data[i] >max) < secmax = max; max = data[i]; >else if (data[i] > secmax && data[i] != max/*removes duplicate problem*/) secmax = data[i]; > return secmax; > int main() < int data[MAX]; // Fill with random integers for (unsigned int i = 0; i < MAX; ++i) < data[i] = rand() % MAX; std::cout std::cout Rajendra Uppal Поделиться