Найти два наименьших (минимальных) элемента массива

Задача

В одномерном массиве целых чисел определить два наименьших элемента. Они могут быть как равны между собой (оба являться минимальными), так и различаться.

Пояснение к задаче и алгоритм решения

Сначала можно найти минимальный элемент массива. После этого искать второй минимум, исключив их поиска первый с помощью if. Данный способ рассматривается здесь по отношению к двум наибольшим элементам.

Сложнее задачу решить, используя один цикл перебора.

Предположим, что двумя наименьшими элементами массива являются первый и второй элемент. Присвоим их индексы переменным m1 и m2. При этом, если первый элемент меньше второго, то его индекс присвоим m1, иначе m1 получит значение второго элемента, а m2 первого.

Начнем перебирать массив в цикле, начиная с третьего элемента. Если он меньше элемента, чей индекс хранится в m1, то присвоим индекс текущего элемента m1. Иначе (если значение по индексу m1 меньше, чем по индексу i) будем проверять, не меньше ли значение по индексу i, того что по индексу m2.

Есть один не очевидный нюанс. Допустим, в m1 указывало на значение 5, а m2 - на 10. Очередной элемент равен 3. Мы меняем m1, и забываем о числе 5. Однако оно может оказаться как раз вторым минимумом массива.

Поэтому в программе при изменении значения m1 надо предусмотреть проверку, не меньше ли теряемое значение, чем то, что хранится по индексу m2.

Исходный код на языке программирования Pascal

const
    N = 10;
var
    a: array[1..N] of integer;
    i, min1, min2, buff: byte;
begin
    randomize;
    for i:=1 to N do begin
        a[i] := random(100);
        write(a[i]:4);        
    end;
    writeln;
   
    if a[1] < a[2] then begin
        min1 := 1;
        min2 := 2;
    end
    else begin
        min1 := 2;
        min2 := 1;
    end;
   
    for i:=3 to N do
        if a[i] < a[min1] then begin
            buff := min1;
            min1 := i;
            if a[buff] < a[min2] then
                min2 := buff;
        end
        else
            if a[i] < a[min2] then
                min2 := i;    
               
    writeln('№', min1:2,': ', a[min1]:2);
    writeln('№', min2:2,': ', a[min2]:2);
end.

Пример(ы) выполнения программы на языке Pascal

   8  66  40  40   0  14  50  74  93  71
5:  0
1:  8

Исходный код на языке программирования C

#include <stdio.h>
#define N 10
main() {
    int a[N];
    int i, min1, min2, buff;
    srand(time(NULL));
    for (i=0; i<N; i++) {
        a[i] = rand() % 100;
        printf("%3d", a[i]);
    }
    printf("\n");
   
    if (a[0] < a[1]) {
        min1 = 0;
        min2 = 1;
    } else {
        min1 = 1;
        min2 = 0;
    }
   
    for (i=2; i<N; i++) {
        if (a[i] < a[min1]) {
            buff = min1;
            min1 = i;
            if (a[buff] < a[min2]) min2 = buff;
        } else {
            if (a[i] < a[min2]) min2 = i;
        }
    }
   
    printf("№%2d:%3d\n",min1+1,a[min1]);
    printf("№%2d:%3d\n",min2+1,a[min2]);
}

Пример(ы) выполнения программы на языке C

 97 20 88 29 20 43 87 19 33 26
8: 19
5: 20

Исходный код на языке программирования Python

from random import random
N = 10
a = []
for i in range(N):
    a.append(int(random()*100))
    print("%3d" % a[i], end='')
print()
 
if a[0] > a[1]:
    min1 = 0
    min2 = 1
else:
    min1 = 1
    min2 = 0
   
for i in range(2,N):
    if a[i] < a[min1]:
        b = min1
        min1 = i
        if a[b] < a[min2]:
            min2 = b
    elif a[i] < a[min2]:
        min2 = i
       
print("№%3d:%3d" % (min1+1, a[min1]))
print("№%3d:%3d" % (min2+1, a[min2]))

Пример(ы) выполнения программы на языке Python

 14  3 40 56 42 43 89 69 64 72
№  1: 14
№  2:  3

Исходный код на языке программирования КуМир

алг два минимальных
нач
    цел N = 10
    цел таб arr[1:N]
    цел i,m1,m2,b
    нц для i от 1 до N
        arr[i] := irand(10,100)
        вывод arr[i]:3
    кц
    вывод нс

    если arr[1] < arr[2] то
        m1 := 1
        m2 := 2
    иначе
        m1 := 2
        m2 := 1
    все

    нц для i от 3 до N
        если arr[i] < arr[m1] то
            b := m1
            m1 := i
            если arr[b] < arr[m2] то
                m2 := b
            все
        иначе
            если arr[i] < arr[m2] то
                m2 := i
            все
        все
    кц
    вывод "№",m1:2,":",arr[m1]:3,нс
    вывод "№",m2:2,":",arr[m2]:3,нс
кон

Пример(ы) выполнения программы на языке КуМир

 65 32 24 86 65 58 67 55 33 96
3: 24
2: 32

Исходный код на языке программирования Basic

N = 10
dim arr(N)
for i=0 to N-1
    arr[i] = int(rand*100)
    print arr[i] + " ";
next i
print

if arr[0] < arr[1] then
    m1 = 0
    m2 = 1
else
    m1 = 1
    m2 = 0
endif

for i=2 to N-1
    if arr[i] < arr[m1] then
        b = m1
        m1 = i
        if arr[b] < arr[m2] then
            m2 = b
        endif
    else
        if arr[i] < arr[m2] then
             m2 = i
        endif
    endif
next i

print (m1+1) + ": " + arr[m1]
print (m2+1) + ": " + arr[m2]

Пример(ы) выполнения программы на языке Basic

81 7 25 71 23 9 56 91 73 64
2: 7
6: 9

Тема

Массивы

Уровень сложности

Средний

Дата публикации

Комментарий

var a:array[1..10000] of integer;
begin
var n:=readlnInteger();
for var i:=1 to n do read(a[i]);
var mf:=a[1];
for var i:=1 to n do if a[i]<mf then mf:=a[i];
print(mf);
for var i:=1 to n do if a[i]=mf then a[i]:=mf+1;
mf:=a[1];
for var i:=1 to n do if a[i]<mf then mf:=a[i];
print(mf);
end.