Как найти самый большой элемент массива python

Условие

Дан список чисел. Выведите значение наибольшего элемента в списке, а затем индекс этого элемента в списке. Если наибольших элементов несколько, выведите индекс первого из них.

Решение

index_of_max = 0 a = [int(i) for i in input().split()] for i in range(1, len(a)): if a[i] > a[index_of_max]: index_of_max = i print(a[index_of_max], index_of_max)

Прошу прощения, что так долго пропадал. Питошка вернулся, да еще и с группой в вконтакте, подписывайтесь. Помимо этого, на питошке откроется новая рубрика, в которой будут четкие объяснения всех заданий ЕГЭ и ОГЭ по информатике, внимательно прочитав которые, я уверен, вы улучшите свои баллы на экзамене ��

Решение на python задач с2 егэ по информатике на поиск максимального элемента массива

Решение на python задач с номером 25 егэ по информатике на поиск максимального элемента массива

В задачах с номером 25 егэ по информатике на поиск максимального элемента необходимо организовать ввод массива с клавиатуры, найти максимальный элемент массива, удовлетворяющий определенному условию. Разберем пример программы на python, которая ищет максимальный четный и максимальный нечетный элемент массива.
Код на Python для ввода с клавиатуры массива заданного размера. Подробно о работе с массивами в Python
a = []
n=10
for i in range(0, n):
a.append(int(input()))
Для максимального четного и нечетного элемента введем переменные и сначал присвоим им занечния первого элемента массива
maxc=a[0]
maxn=a[0]
В цикле for переберём все элементы массива и с помощью оператора условия в python if
сравним каждый нечетный элемент массива с текущим значением максимума, если этот элемент будет больше, то текущему максимуму присвоим значение этого элемента массива.
Чтобы проверить, является ли переменная четной, в условии нужно использовать выражение
переменная%2==0
Чтобы проверить, является ли переменная нечетной, в условии нужно использовать выражение
переменная%2!=0
Чтобы одновременно выполнялись оба условия, в условии if необходимо использовать логическую операцию and Подробно об условиях If в python
for i in range(0, n):
if a[i]%2==0 and a[i]>maxc:
maxc=a[i]
if a[i]%2!=0 and a[i]>maxn:
maxn=a[i]

Полная программа на Python, которая ищет максимальный четный и нечетный элемент массива
a = []
n=10
for i in range(0, n):
a.append(int(input()))
maxc=a[0]
maxn=a[0]
for i in range(0, n):
if a[i]%2==0 and a[i]>maxc:
maxc=a[i]
if a[i]%2!=0 and a[i]>maxn:
maxn=a[i]
print(‘максимальный четный элемент’,maxc)
print(‘максимальный нечетный элемент’,maxn)
Разберем решение на python задачи с номером 25 егэ по информатике на поиск максимального элемента массива.
Дан целочисленный массив из 10 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно Необходимо написать программу, которая позволяет найти и вывести максимальное значение среди двухзначных элементов массива, делящихся на 7. Если в исходном массиве нет элемента, значение которого является трёхзначным числом и при этом кратно 7, то вывести сообщение «Не найдено».

Организуем ввод массива с клавиатуры в python
a = []
n=10
for i in range(0, n):
a.append(int(input()))
max=1
Введем переменную max в которую будем записывать максимальное значение двузначных элементов массива. присвоим ей в начале программы значение 1. Если элементы удовлетворяющие нужному нам условию не будут найдены, то значение переменной max останется равным 1, это будет говорить о том что элементы не найдены
В цикле for перебираем все элементы массива и ищем максимум среди двузначных чисел
Двузначные элементы лежат в диапазоне от 10 до 99. Чтобы элемент был двузначным и делился на 7 в операторе условия необходимо, чтобы выполнялось сразу три условия одновременно
a[i]>9, a[i] Чтобы выполнялись все три условия необходимо в операторе условия If использовать логическую операцию and
for i in range(0, n):
if a[i]>9 and a[i] max=a[i]
В конце программы производится проверка найден ли хотя бы один элемент удовлетворяющий условию задачи, если элементы не найдены то выводится сообщение элементы не найдены
if max==1:
print(‘элементы не найдены’)
else:
print(‘максимальный элемент ‘, max)

Полная программа на python для поиска максимального двузначного элемента массива кратного 7
a = []
n=10
for i in range(0, n):
a.append(int(input()))
max=1
for i in range(0, n):
if a[i]>9 and a[i]max:
max=a[i]
if max==1:
print(‘элементы не найдены’)
else:
print(‘максимальный элемент ‘, max)

Полезно почитать по теме решение на python задач с номером 25 егэ по информатике на тему массивы

Найти k-й самый большой элемент в массиве

Для заданного массива целых чисел найдите k-й по величине элемент в массиве, где k — целое положительное число, меньшее или равное длине массива.

Input:

arr = [7, 4, 6, 3, 9, 1]
k = 2

Output:

The 2nd largest array element is 7

Простым решением было бы использовать эффективный алгоритм сортировки чтобы отсортировать массив в порядке убывания и вернуть элемент в (k-1)’th индекс. Временная сложность этого подхода в наихудшем случае будет O(n.log(n)) , куда n это размер ввода. Мы можем улучшить временную сложность, используя следующие методы:

Использование минимальной кучи

Мы можем легко решить эту проблему в O(n.log(k)) с помощью min-heap . Идея состоит в том, чтобы построить мини-кучу размера k и вставьте первый k элементы массива A[0…k-1] в мини-кучу. Затем для каждого из оставшихся элементов массива A[k…n-1] , если этот элемент больше, чем корень минимальной кучи, замените корень текущим элементом. Повторяйте этот процесс, пока массив не будет исчерпан. Теперь у нас останется верх k самые большие элементы массива в минимальной куче, и k’th самый большой элемент будет находиться в корне минимальной кучи.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

using namespace std ;
// Функция для поиска k-го по величине элемента в массиве с использованием минимальной кучи
int findKthLargest ( vector < int >const &ints , int k )
// базовый вариант
if ( ints . size ( ) < k ) < // создаем мини-кучу с помощью `std::priority_queue` и вставляем // первые `k` элементов массива в кучу // `std::greater` используется как функция сравнения для min-heap priority_queue < int , vector < int >, greater < int >> pq ( ints . begin ( ) , ints . begin ( ) + k ) ;
// делаем для оставшихся элементов массива
for ( int i = k ; i < ints . size ( ) ; i ++ ) // если текущий элемент больше, чем корень кучи if ( ints [ i ] > pq . top ( ) )
// заменить корень текущим элементом
pq . push ( ints [ i ] ) ;
// возвращаем корень min-heap
return pq . top ( ) ;
vector < int >ints = < 7 , 4 , 6 , 3 , 9 , 1 >;
cout << "k'th largest array element is " << findKthLargest ( ints , k ) ;

результат:

k’th largest array element is 7

Java

import java . util . Arrays ;
import java . util . List ;
import java . util . PriorityQueue ;
class Main
// Функция для поиска k-го по величине элемента в массиве с использованием минимальной кучи
public static int findKthLargest ( List ints , int k )
// базовый вариант
if ( ints == null || ints . size ( ) < k ) < System . exit ( - 1 ) ; // создаем мини-кучу с помощью класса PriorityQueue и вставляем // первые `k` элементов массива в кучу PriorityQueue pq = new PriorityQueue <> ( ints . subList ( 0 , k ) ) ;
// делаем для оставшихся элементов массива
for ( int i = k ; i < ints . size ( ) ; i ++ ) // если текущий элемент больше, чем корень кучи if ( ints . get ( i ) > pq . peek ( ) )
// заменить корень текущим элементом
pq . add ( ints . get ( i ) ) ;
// возвращаем корень min-heap
return pq . peek ( ) ;
public static void main ( String [ ] args )
List ints = Arrays . asList ( 7 , 4 , 6 , 3 , 9 , 1 ) ;
System . out . println ( «k’th largest array element is » + findKthLargest ( ints , k ) ) ;

результат:

k’th largest array element is 7

Python

import heapq
# Функция для поиска k-го по величине элемента в списке с использованием минимальной кучи
def find_kth_largest ( ints , k ) :
# Базовый вариант
if not ints or len ( ints ) < k : # создает мини-кучу из первых `k` элементов в списке pq = ints [ 0 : k ] heapq . heapify ( pq ) # сделать для остальных элементов списка for i in range ( k , len ( ints ) ) : #, если текущий элемент больше, чем корень кучи if ints [ i ] > pq [ 0 ] :
# заменить root текущим элементом
heapq . heapreplace ( pq , ints [ i ] )
# возвращает корень min-heap
return pq [ 0 ]
if __name__ == ‘__main__’ :
ints = [ 7 , 4 , 6 , 3 , 9 , 1 ]
print ( ‘k\’th largest element in the list is’ , find_kth_largest ( ints , k ) )

результат:

k’th largest element in the list is 7

Использование максимальной кучи

Мы можем легко решить эту проблему в O(n + k.log(n)) с помощью max-heap . Идея состоит в том, чтобы просто построить максимальную кучу размера n и вставляем все элементы массива [0…n-1] внутрь. Тогда поп сначала k-1 элементы из него. В настоящее время k’th самый большой элемент будет находиться в корне максимальной кучи.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

C++

using namespace std ;
// Функция для поиска k-го по величине элемента в массиве с использованием max-heap
int findKthLargest ( vector < int >const &ints , int k )
// базовый вариант
if ( ints . size ( ) < k ) < // создаем максимальную кучу, используя `std::priority_queue` // из всех элементов вектора priority_queue < int , vector < int >> pq ( less < int >( ) , ints ) ;
// извлечь из max-heap ровно `k-1` раз
// возвращаем корень max-heap
return pq . top ( ) ;
vector < int >ints = < 7 , 4 , 6 , 3 , 9 , 1 >;
cout << "k'th largest array element is " << findKthLargest ( ints , k ) ;

результат:

k’th largest array element is 7

Java

import java . util . Arrays ;
import java . util . List ;
import java . util . PriorityQueue ;
class Main
// Функция для поиска k-го по величине элемента в массиве с использованием max-heap
public static int findKthLargest ( List ints , int k )
// базовый вариант
if ( ints == null || ints . size ( ) < k ) < System . exit ( - 1 ) ; // строим максимальную кучу, используя класс PriorityQueue из всех // элементы в списке PriorityQueue pq = new PriorityQueue <> ( ( a , b ) -> b — a ) ;
// или передать `Comparator.reverseOrder()`
pq . addAll ( ints ) ;
// извлечь из max-heap ровно `k-1` раз
while ( — k > 0 ) < // возвращаем корень max-heap return pq . peek ( ) ; public static void main ( String [ ] args ) List ints = Arrays . asList ( 7 , 4 , 6 , 3 , 9 , 1 ) ;
System . out . println ( «k’th largest array element is » + findKthLargest ( ints , k ) ) ;

результат:

k’th largest array element is 7

Python

import heapq
# Простая реализация max-heap на основе heapq.
class MaxHeap :
def __init__ ( self , data = None ) :
if data is None :
self . data = [ ]
self . data = [ — i for i in data ]
heapq . heapify ( self . data )
def top ( self ) :
return — self . data [ 0 ]
def push ( self , item ) :
heapq . heappush ( self . data , — item )
def pop ( self ) :
return — heapq . heappop ( self . data )
def replace ( self , item ) :
return heapq . heapreplace ( self . data , — item )
# Функция для поиска k-го по величине элемента в списке с использованием max-heap
def find_kth_largest ( ints , k ) :
# Базовый вариант
if not ints or len ( ints ) < k : # строит max-heap из всех элементов в списке pq = MaxHeap ( ints ) # выталкивает из max-heap ровно `k-1` раз while k > 1 :
# возвращает корень max-heap
return pq . top ( )
if __name__ == ‘__main__’ :
ints = [ 7 , 4 , 6 , 3 , 9 , 1 ]
print ( ‘k\’th largest element in the list is’ , find_kth_largest ( ints , k ) )

результат:

k’th largest element in the list is 7

Использование STL

Мы можем легко решить эту проблему, используя std::nth_element в C++. Отдельное спасибо читателю за то, что поделился этим подходом в комментариях. Ниже приведен прототип std::nth_element , который переставляет элементы в диапазоне [first, last) так что элемент в n’th position — это элемент, который будет находиться в этой позиции в отсортированной последовательности:

void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last)

std::nth_element обычно реализуется с использованием версии быстрый выбор называется интроселект. Introselect — это гибрид быстрого выбора и медиана медиан. Если быстрый выбор занимает слишком много времени (плохой опорный выбор), он возвращается к более медленному, но гарантированному алгоритму линейного времени, тем самым ограничивая время выполнения в наихудшем случае, прежде чем он станет хуже, чем линейный.