Как найти три минимума в массиве

Вот накидал с достаточно подробными, для того чтобы разобраться самому, комментариями программу, которая работает без сортировки за линейное время. Идея в том, чтобы проходя однократно по массиву поддерживать акутальными текущие три минимальные числа, обновляя их с учетом каждого последующего элемента массива. Это решение легко расширяется на поиск любого фиксированного числа N минимальных элементов, не только трех.

P.S. Для ArrayList с алгоритмической точки зрения все делается точно так же. Я написал, как мне проще и быстрее, чтобы объяснить суть решения, а не конкретную техническую реализацию.

class Test {

  // Здесь будут храниться наши три минимальные числа.
  static int min[] = {Integer.MAX_VALUE, Integer.MAX_VALUE, Integer.MAX_VALUE};

  // Обновляем массив `min` имея новое число-кандидат в минимум.
  static void updateMin(int x) {
    // Перебираем текущие минимальные числа.
    for (int i = 0; i < 3; ++i) {
      if (x < min[i]) {
        // Новое число меньше рассматриваемого из `min`.

        // Сдвигаем текущее и последующие числа, чтобы освободить место
        // для нового.
        for (int j = 2; j > i; --j)
          min[j] = min[j - 1];

        // Вставляем новое число на полагающееся ему место.
        min[i] = x;

        // Дело сделано.
        return;
      } else if (x == min[i]) {
        // Новое число равно рассматриваемому из `min`.

        // Заканчиваем, т.к. такое число уже есть среди минимальных.
        return;
      }

      // Иначе переходим к следующему числу из `min`
    }
  }

  public static void main(String[] args) {
    int loc[] = {25, 11, 250, 5, 45, 8, 10, 45, 31, 123, 489};

    // Находим три минимальных числа.
    for (int i = 0; i < loc.length; ++i)
      updateMin(loc[i]);

    // Выводим их
    // (проверка на MAX_VALUE на случай, если минимальных чисел окажется
    //  меньше трех).
    for (int i = 0; i < 3 && min[i] != Integer.MAX_VALUE; ++i)
      System.out.println(min[i]);
  }
}

Источник

Improve Article

Save Article

Like Article

  • Read
  • Discuss

    • Improve Article

    Save Article

    Like Article

    Find the first, second and third minimum elements in an array in O(n).

    Examples: 

    Input : 9 4 12 6
Output : First min = 4
         Second min = 6
         Third min = 9

Input : 4 9 1 32 12
Output : First min = 1
         Second min = 4
         Third min = 9

    First approach : First we can use normal method that is sort the array and then print first, second and third element of the array. Time complexity of this solution is O(n Log n).

    C++

    #include<bits/stdc++.h>

    using namespace std;

    int Print3Smallest(int array[], int n)

    {

        sort(array,array+n);

        cout << "First min = " << array[0] << "n";

        cout << "Second min = " << array[1] << "n";

        cout << "Third min = " << array[2] << "n";

    }

    int main()

    {

        int array[] = {4, 9, 1, 32, 12};

        int n = sizeof(array) / sizeof(array[0]);

        Print3Smallest(array, n);

        return 0;

    }

    Java

    import java.util.Arrays;

    public class Main {

      static void Print3Smallest(int array[], int n) {

      Arrays.sort(array);

          System.out.println("First min = " + array[0]);

          System.out.println("Second min = " + array[1]);

          System.out.println("Third min = " + array[2]);

      }

      public static void main(String[] args) {

          int array[] = {4, 9, 1, 32, 12};

          int n = array.length;

          Print3Smallest(array, n);

      }

    }

    Python3

    def print_3_smallest(array):

        array.sort()

        print("First min =", array[0])

        print("Second min =", array[1])

        print("Third min =", array[2])

    if __name__ == '__main__':

        array = [4, 9, 1, 32, 12]

        n = len(array)

        print_3_smallest(array)

    C#

    using System;

    using System.Linq;

    class Program

    {

        static void Print3Smallest(int[] array, int n)

        {

            Array.Sort(array);

            Console.WriteLine("First min = " + array[0]);

            Console.WriteLine("Second min = " + array[1]);

            Console.WriteLine("Third min = " + array[2]);

        }

        static void Main()

        {

            int[] array = {4, 9, 1, 32, 12};

            int n = array.Length;

            Print3Smallest(array, n);

        }

    }

    Javascript

    function Print3Smallest(array,n){

        array.sort((a, b) => a - b);

        console.log('First min = ' + array[0]);

        console.log('Second min = ' + array[1]);

        console.log('Third min = ' + array[2]);

    }

    let array = [4, 9, 1, 32, 12];

    Print3Smallest(array,array.length);

    Output

    First min = 1
Second min = 4
Third min = 9

    Second approach : Time complexity of this solution is O(n).

    Algorithm:

    • First take an element
    • then if array[index] < Firstelement
      • Thirdelement = Secondelement
      • Secondelement = Firstelement
      • Firstelement = array[index]
    •      else if array[index] < Secondelement
      •   Thirdelement = Secondelement
      •  Secondelement = array[index]
    •      else if array[index] < Thirdelement
      • Thirdelement = array[index]
    • then print all the element 

    Implementation:

    C++

    #include<bits/stdc++.h>

    #define MAX 100000

    using namespace std;

    int Print3Smallest(int array[], int n)

    {

        int firstmin = MAX, secmin = MAX, thirdmin = MAX;

        for (int i = 0; i < n; i++)

        {

            if (array[i] < firstmin)

            {

                thirdmin = secmin;

                secmin = firstmin;

                firstmin = array[i];

            }

            else if (array[i] < secmin)

            {

                thirdmin = secmin;

                secmin = array[i];

            }

            else if (array[i] < thirdmin)

                thirdmin = array[i];

        }

        cout << "First min = " << firstmin << "n";

        cout << "Second min = " << secmin << "n";

        cout << "Third min = " << thirdmin << "n";

    }

    int main()

    {

        int array[] = {4, 9, 1, 32, 12};

        int n = sizeof(array) / sizeof(array[0]);

        Print3Smallest(array, n);

        return 0;

    }

    Java

    import java.util.*;

    public class GFG

    {

        static void Print3Smallest(int array[], int n)

        {

                int firstmin = Integer.MAX_VALUE;

                int secmin = Integer.MAX_VALUE;

                int thirdmin = Integer.MAX_VALUE;

                for (int i = 0; i < n; i++)

                {

                    if (array[i] < firstmin)

                    {

                        thirdmin = secmin;

                        secmin = firstmin;

                        firstmin = array[i];

                    }

                    else if (array[i] < secmin)

                    {

                        thirdmin = secmin;

                        secmin = array[i];

                    }

                    else if (array[i] < thirdmin)

                        thirdmin = array[i];

                }

                System.out.println("First min = " + firstmin );

                System.out.println("Second min = " + secmin );

                System.out.println("Third min = " + thirdmin );

        }

        public static void main(String[] args)

        {

                int array[] = {4, 9, 1, 32, 12};

                int n = array.length;

                Print3Smallest(array, n);

        }

    }

    Python3

    MAX = 100000

    def Print3Smallest(arr, n):

        firstmin = MAX

        secmin = MAX

        thirdmin = MAX

        for i in range(0, n):

            if arr[i] < firstmin:

                thirdmin = secmin

                secmin = firstmin

                firstmin = arr[i]

            elif arr[i] < secmin:

                thirdmin = secmin

                secmin = arr[i]

            elif arr[i] < thirdmin:

                thirdmin = arr[i]

        print("First min = ", firstmin)

        print("Second min = ", secmin)

        print("Third min = ", thirdmin)

    arr = [4, 9, 1, 32, 12]

    n = len(arr)

    Print3Smallest(arr, n)

    C#

    using System;

    class GFG

    {

    static void Print3Smallest(int []array, int n)

        {

                int firstmin = int.MaxValue;

                int secmin = int.MaxValue;

                int thirdmin = int.MaxValue;

                for (int i = 0; i < n; i++)

                {

                    if (array[i] < firstmin)

                    {

                        thirdmin = secmin;

                        secmin = firstmin;

                        firstmin = array[i];

                    }

                    else if (array[i] < secmin)

                    {

                        thirdmin = secmin;

                        secmin = array[i];

                    }

                    else if (array[i] < thirdmin)

                        thirdmin = array[i];

                }

                Console.WriteLine("First min = " + firstmin );

                Console.WriteLine("Second min = " + secmin );

                Console.WriteLine("Third min = " + thirdmin );

        }

        static void Main()

        {

        int []array = new int[]{4, 9, 1, 32, 12};

        int n = array.Length;

        Print3Smallest(array, n);

        }

    }

    PHP

    <?php

    function Print3Smallest($array, $n)

    {

        $MAX = 100000;

        $firstmin = $MAX;

        $secmin = $MAX;

        $thirdmin = $MAX;

        for ($i = 0; $i < $n; $i++)

        {

            if ($array[$i] < $firstmin)

            {

                $thirdmin = $secmin;

                $secmin = $firstmin;

                $firstmin = $array[$i];

            }

            else if ($array[$i] < $secmin)

            {

                $thirdmin = $secmin;

                $secmin = $array[$i];

            }

            else if ($array[$i] < $thirdmin)

                $thirdmin = $array[$i];

        }

        echo "First min = ".$firstmin."n";

        echo "Second min = ".$secmin."n";

        echo "Third min = ".$thirdmin."n";

    }

        $array= array(4, 9, 1, 32, 12);

        $n = sizeof($array) / sizeof($array[0]);

        Print3Smallest($array, $n);

    ?>

    Javascript

    <script>

    let MAX = 100000

    function Print3Smallest( array,  n)

    {

        let firstmin = MAX, secmin = MAX, thirdmin = MAX;

        for (let i = 0; i < n; i++)

        {

            if (array[i] < firstmin)

            {

                thirdmin = secmin;

                secmin = firstmin;

                firstmin = array[i];

            }

            else if (array[i] < secmin)

            {

                thirdmin = secmin;

                secmin = array[i];

            }

            else if (array[i] < thirdmin)

                thirdmin = array[i];

        }

        document.write("First min = " + firstmin + "</br>");

        document.write("Second min = " + secmin + "</br>");

        document.write("Third min = " + thirdmin + "</br>");

    }

        let array = [4, 9, 1, 32, 12];

        let n = array.length;

        Print3Smallest(array, n);

    </script>

    Output

    First min = 1
Second min = 4
Third min = 9

    Time Complexity: O(n)
    Auxiliary Space: O(1)

    Last Updated :
    09 Mar, 2023

    Like Article

    Save Article

    Источник

    Поиск 3-х минимальных элементов


    This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
    Learn more about bidirectional Unicode characters

    Show hidden characters

    package com.company;
    import java.util.Arrays;
    import java.util.Random;
    /**
    * Поиск 3 минимальных элементов массива
    */
    public class MinElement {
    private static int min1 = 0;
    private static int min2 = 0;
    private static int min3 = 0;
    static int[] a;
    // Заполнение массива случайными числами
    public void fillArray(int[] a) {
    if (a.length > 0) {
    Random random = new Random();
    for (int i = 0; i < a.length; i++) {
    a[i] = random.nextInt(100);
    }
    }
    }
    // Вывод массива в консоль
    public void printArray(int[] a) {
    for (int i = 0; i < a.length; i++) {
    System.out.printf(«%3d «, a[i]);
    }
    }
    // Поиск 3-х минимальных элементов
    public void findMinElements() {
    for (int i = 3; i < a.length; i++) {
    if (min1 > a[i]) {
    min3 = min2;
    min2 = min1;
    min1 = a[i];
    } else if (min2 > a[i]) {
    min3 = min2;
    min2 = a[i];
    } else if (min3 > a[i]) {
    min3 = a[i];
    }
    }
    }
    // Сортирует первые 3 минимальные значения в порядке min1 < min2 < min3
    public void sortMinElementAtBegining() {
    int temp = 0;
    if (min2 > min3) {
    temp = min2;
    min2 = min3;
    min3 = temp;
    }
    if (min1 > min2 && min1 > min3) {
    temp = min1;
    min1 = min2;
    min2 = min3;
    min3 = temp;
    } else if (min1 > min2) {
    temp = min1;
    min1 = min2;
    min2 = temp;
    }
    }
    public static void main(String[] args) {
    MinElement minElement = new MinElement();
    a = new int[20];
    minElement.fillArray(a);
    System.out.println(«Исходный массив:»);
    minElement.printArray(a);
    min1 = a[0];
    min2 = a[1];
    min3 = a[2];
    minElement.sortMinElementAtBegining();
    minElement.findMinElements();
    System.out.printf(«nРезультат:n«);
    System.out.println(«min1 = « + min1);
    System.out.println(«min2 = « + min2);
    System.out.println(«min3 = « + min3);
    Arrays.sort(a);
    System.out.println(«Сортированный массив (проще проверить правильность поиска):»);
    minElement.printArray(a);
    }
    }
    Источник

    есть массив из 5-10 цифр, может и больше, надо найти 3 минимальных числа, понимаю как найти 2, но как найти 3 что-то придумать не могу


    • Вопрос задан

      более трёх лет назад

    • 329 просмотров

    Источник

    Формулировка задачи:

    уважаемые, дана задача мне, найти три минимума в массиве.
    дословное условие:

    «Напишите программу, которая находит в массиве три минимальных элемента, то есть три первых элемента массива после сортировки по возрастанию.

    Входные данные
    Первая строка содержит размер массива N . Во второй строке через пробел задаются N чисел – элементы массива. Гарантируется, что 3 < N ≤ 10000 .

    Выходные данные
    Программа должна вывести в одной строке три минимальных элемента массива в порядке возрастания, разделив их пробелами.»
    мой код:

    но при загрузке этого кода в систему, компьютер выдает только 1 верное решение из 23
    в чем ошибка?

    Код к задаче: «Найти три минимума в массиве»

    textual

    := 
    (integer.MaxValue, integer.MaxValue, integer.MaxValue)

    Полезно ли:

    8   голосов , оценка 4.000 из 5

    Источник

    Понравилась статья? Поделить с друзьями:
  • Как найти ответы на тест по биологии
  • Яндекс избранное коллекция как найти
  • Как найти хост контроллеры шины ieee 1394
  • Как найти расположение машины
  • Как составить словосочетание с собирательным числительным