Как найти два минимальных значения - Сайт, где вы сможете решить свои вопросы

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

Просмотров 7.5к. Обновлено 15 октября 2021

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

Сначала можно найти минимальный элемент массива. После этого искать второй минимум, исключив их поиска первый с помощью 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.





   8  66  40  40   0  14  50  74  93  71

№ 5:  0

№ 1:  8

Язык Си



#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:%3dn",min1+1,a[min1]);

    printf("№%2d:%3dn",min2+1,a[min2]);

}





 97 20 88 29 20 43 87 19 33 26

№ 8: 19

№ 5: 20

Python

найти два минимальных элемента массива 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]))



# Вариант 2 


from random import randint


array = [randint(1, 20) for i in range(10)]

print(array)


min1 = min(array)

array.remove(min1)

min2 = min(array)


print(min1)

print(min2)





 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-256



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]





81 7 25 71 23 9 56 91 73 64 

2: 7

6: 9

Источник

igorbukur

0 / 0 / 1

Регистрация: 02.02.2016

Сообщений: 128

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

07.06.2018, 18:59. Показов 8567. Ответов 3

Метки нет (Все метки)

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

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

C++

#include <iostream>
 
using namespace std;
 
void main() {
    setlocale(LC_ALL, "rus"); 
    int arr[10];
    int temp1 , temp2; 
    int d= 0, j =0;
 
    for (int i =0; i < 10; i++) {
        arr[i] = 1 + rand() % 10000;
        cout << "Элемент массива " << i << ": " << arr[i] << endl;
    }
    temp1 = arr[0];
    temp2 = arr[1];
 
    for (int i =0; i < 10; i++) {
        if (arr[i] < temp1) {
            temp1 = arr[i];
            d = i;
        }
    }
 
    for (int i = 0; i < 10; i++) {
        if (i != d) {
            if (arr[i] < temp2) {
                temp2 = arr[i];
                j = i;
            }
        }
    }

Добавлено через 7 минут
Да и вообще мол можно сделать короче и компактнее.

SuperKir

473 / 425 / 290

Регистрация: 10.03.2015

Сообщений: 1,782

07.06.2018, 19:12

C++

#include <iostream>
#include <ctime>
 
int main()
{
    srand(time(NULL));
    int arr[10];
    for (int i = 0; i < 10; i++)
    {
        arr[i] = 1 + rand() % 10000;
        std::cout << i << ": " << arr[i] << std::endl;
    }
 
    int min1 = arr[0], min2 = arr[1];
    if (min2 < min1)
    {
        min1 = arr[1];
        min2 = arr[0];
    }
    for (int i = 2; i < 10; i++)
    {
        if (arr[i] < min1)
        {
            min2 = min1;
            min1 = arr[i];
        }
        else if (arr[i] < min2)
            min2 = arr[i];
 
    }
    std::cout << min1 << " " << min2 << std::endl; 
 
    system("pause");
    return 0;
}

Yetty

7427 / 5021 / 2891

Регистрация: 18.12.2017

Сообщений: 15,694

08.06.2018, 00:20

igorbukur, по условию массив размер массива произвольный и не обязательно целочисленный. задавайте размер массива и используйте тип double для его элементов. можно так:

C++

#include <iostream>
#include <ctime>
using namespace std; 
 
int main()
{
    srand((int)time(0)); 
    int n, imin=0;
    cout <<"n="; cin >>n;
 
    double*a = new double[n], min1, min2;
    
    for (int i = 0; i <n; i++)
    {
        a[i]=rand()%10000+1;
        if (i==0 || a[i]<min1) {min1=a[i];imin=i;}        
        cout <<i<<": "<<a[i]<<endl;
    }
    
    a[imin]=a[0];
    for (int i = 1; i < n; i++)
    if (i==1 || a[i]<min2) min2=a[i];    
    cout <<min1<<" "<<min2<<endl;
    delete[]a;
system("pause");
return 0;
}

или так:

C++

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
using namespace std; 
 
int main()
{
    srand((int)time(0));
    int n;
    cout <<"n="; cin >>n;
    
    vector<double> a(n);
    
    for (int i = 0; i < n; i++)
    {
        a[i]=rand()%10000+1;               
        cout <<i<<": "<<a[i]<<endl;
    }    
    sort(a.begin(), a.end());    
    cout <<a[0]<<" "<<a[1]<<" "<<endl;  
system("pause");
return 0;
}

trifecta

19 / 17 / 7

Регистрация: 18.09.2017

Сообщений: 95

08.06.2018, 05:29

Сообщение от igorbukur

можно сделать короче и компактнее

Можно.

C++

#include <algorithm>
#include <iterator>
//...
nth_element(begin(arr), begin(arr) + 1, end(arr));
cout << arr[0] << endl
     << arr[1] << endl;

Источник

Помогите =( Находится второе число, но совершенно другое, пробовал через отладчик найти, не могу понять в чем проблема.

        int[] a = new int[] { 5, 12, 13, 2, 1, 9, 15, 19, 6 };
        int oneMinValue = a[0];
        int twoMinValue = a[0];
        for (int i = 0; i < a.Length; i++)
        {
            if (oneMinValue > a[i])
            {
                oneMinValue = a[i];
            }
         else if (twoMinValue > a[i] & twoMinValue <= oneMinValue)
            {
                twoMinValue = a[i];
            }


        }

        for (int i = 0; i < a.Length; i++)
        {
            Console.WriteLine(oneMinValue);
            Console.WriteLine(twoMinValue);
        }

Harry

214k15 золотых знаков117 серебряных знаков227 бронзовых знаков

задан 23 авг 2022 в 14:28

Вам надо не забывать, что инвариант — oneMinValue не превышает twoMinValue.

Так что вот как должно быть…

        for (int i = 0; i < a.Length; i++)
        {
            if (twoMinValue > a[i])
            {
                twoMinValue = a[i];
            }
            if (twoMinValue < oneMinValue)
            {
                int tmp = twoMinValue;
                twoMinValue = oneMinValue;
                oneMinValue = tmp;
            }

        }

Ну и выводить в цикле совсем ни к чему:

        Console.WriteLine(oneMinValue);
        Console.WriteLine(twoMinValue);

Вот, смотрите результат.

Update

По замечанию DmitryK:

        int oneMinValue = a[0];
        int twoMinValue = a[1];

        if (twoMinValue < oneMinValue)
        {
            int tmp = twoMinValue;
            twoMinValue = oneMinValue;
            oneMinValue = tmp;
        }

        for (int i = 2; i < a.Length; i++)
        {
            if (twoMinValue > a[i])
            {
                twoMinValue = a[i];
            }
            if (twoMinValue < oneMinValue)
            {
                int tmp = twoMinValue;
                twoMinValue = oneMinValue;
                oneMinValue = tmp;
            }

        }

ответ дан 23 авг 2022 в 14:35

HarryHarry

214k15 золотых знаков117 серебряных знаков227 бронзовых знаков

У вас условие никогда не выполняется.

if (twoMinValue > a[i] & twoMinValue <= oneMinValue)

Поскольку oneMinValue при проходе по массиву всегда является минимальным из уже встреченных чисел, то условие twoMinValue <= oneMinValue всегда ложное.
Должно быть что-то вроде такого:

int oneMinValue = a[0];
int twoMinValue = a[1];

if(oneMinValue > twoMinValue)
   swap(oneMinValue, twoMinValue);

for (int i = 0; i < a.Length; i++)
   if (oneMinValue > a[i])
   {  
      twoMinValue = oneMinValue;
      oneMinValue = a[i];
   }
   else
   if(twoMinValue > a[i])
      twoMinValue = a[i];

ответ дан 23 авг 2022 в 14:35

DmitryKDmitryK

4,4631 золотой знак5 серебряных знаков19 бронзовых знаков

Источник

I’d like to add another, more general approach:
Here’s a recursive way of finding the i-th minimums of a given list of numbers

def find_i_minimums(numbers,i):
    minimum = float('inf')
    if i==0:
        return []
    less_than_i_minimums = find_i_minimums(numbers,i-1)
    for element in numbers:
        if element not in less_than_i_minimums and element < minimum:
            minimum = element
    return less_than_i_minimums + [minimum]

For example,

>>> find_i_minimums([0,7,4,5,21,2,6,1],3) # finding 3 minimial values for the given list
[0, 1, 2]

( And if you want only the i-th minimum number you’d extract the final value of the list )

The time-complexity of the above algorithm is bad though, it is O(N*i^2) ( Since the recursion depth is i , and at each recursive call we go over all values in ‘numbers’ list whose length is N and we check if the minimum element we’re searching for isn’t in a list of length i-1, thus the total complexity can be described by a geometric sum that will give the above mentioned complexity ).

Here’s a similar but alternative-implementation whose time-complexity is O(N*i) on average. It uses python’s built-in ‘set’ data-structure:

def find_i_minimums(numbers,i):
    minimum = float('inf')
    if i==0:
        return set()
    less_than_i_minimums = find_i_minimums(numbers,i-1)
    for element in numbers:
        if element not in less_than_i_minimums and element < minimum:
            minimum = element
    return less_than_i_minimums.union(set({minimum}))

If your ‘i’ is small, you can use the implementations above and then extract how many minimums you want ( or if you want the second minimum, then in your case run the code for i=2 and just extract the last element from the output data-structure ).
But if ‘i’ is for example greater than log(N) , I’d recommend sorting the list of numbers itself ( for example, using mergesort whose complexity is O(N*log(N)) at worst case ) and then taking the i-th element. Why so? because as stated, the run-time of the algorithm above is not great for larger values of ‘i’.

Источник

Функция действительно может быть изменена, чтобы найти вторую наименьшую:

def second_smallest(numbers):
    m1, m2 = float('inf'), float('inf')
    for x in numbers:
        if x <= m1:
            m1, m2 = x, m1
        elif x < m2:
            m2 = x
    return m2

Старая версия основывалась на деталях реализации Python 2, которые None всегда сортируются перед чем-либо еще (поэтому он тестируется как “меньше” ); Я заменил это с помощью float('inf') как дозорного, так как бесконечность всегда проверяется как больше любого другого числа. В идеале исходная функция должна была использовать float('-inf') вместо None там, чтобы не привязываться к деталям реализации, другие реализации Python могут не делиться.

Демо:

>>> def second_smallest(numbers):
...     m1, m2 = float('inf'), float('inf')
...     for x in numbers:
...         if x <= m1:
...             m1, m2 = x, m1
...         elif x < m2:
...             m2 = x
...     return m2
... 
>>> print second_smallest([1, 2, 3, 4])
2

Вне функции, которую вы обнаружили, почти так же эффективно использовать функцию heapq.nsmallest(), чтобы вернуть два наименьших значения из iterable, и из этих двух выбрать второе (или последнее) значение:

from heapq import nsmallest

def second_smallest(numbers):
    return nsmallest(2, numbers)[-1]

Как и вышеприведенная реализация, это решение O (N); сохраняя вариант кучи, каждый шаг принимает время logK, но K является константой здесь (2)! Что бы вы ни делали, не используйте сортировку; который принимает время O (NlogN).

Источник

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

Pascal

Язык Си

Python

КуМир

Basic-256

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

Вам также может понравиться

Параллелепипед как найти его обьем

Как найти друзей в инсте через контакты

Тесто для пиццы жесткое как исправить

Добавить комментарий Отменить ответ