Рубрики

Найти самые маленькие и вторые самые маленькие элементы в массиве

Напишите эффективную программу на C, чтобы найти самый маленький и второй самый маленький элемент в массиве.

Пример :

Input:  arr[] = {12, 13, 1, 10, 34, 1}
Output: The smallest element is 1 and 
        second Smallest element is 10

Простое решение — отсортировать массив в порядке возрастания. Первые два элемента в отсортированном массиве будут двумя наименьшими элементами. Временная сложность этого решения составляет O (n Log n).

Лучшее решение состоит в том, чтобы сканировать массив дважды. При первом обходе найдите минимальный элемент. Пусть этот элемент будет х. Во втором обходе найдите наименьший элемент больше x. Временная сложность этого решения составляет O (n).

Приведенное выше решение требует двух обходов входного массива.

Эффективное решение может найти как минимум два элемента в одном обходе. Ниже приведен полный алгоритм.

Алгоритм:

1) Initialize both first and second smallest as INT_MAX
   first = second = INT_MAX
2) Loop through all the elements.
   a) If the current element is smaller than first, then update first 
       and second. 
   b) Else if the current element is smaller than second then update 
    second

Реализация:

C ++

// C ++ программа для поиска самых маленьких и
// вторые самые маленькие элементы
#include <bits/stdc++.h>

using namespace std; / * Для INT_MAX * /

  

void print2Smallest(int arr[], int arr_size) 

    int i, first, second; 

  

    / * Должно быть как минимум два элемента * /

    if (arr_size < 2) 

    

        cout<<" Invalid Input "

        return

    

  

    first = second = INT_MAX; 

    for (i = 0; i < arr_size ; i ++) 

    

        / * Если текущий элемент меньше первого

        затем обновите первый и второй * /

        if (arr[i] < first) 

        

            second = first; 

            first = arr[i]; 

        

  

        / * Если arr [i] находится между первым и вторым

        затем обновите второй * /

        else if (arr[i] < second && arr[i] != first) 

            second = arr[i]; 

    

    if (second == INT_MAX) 

        cout << "There is no second smallest element\n"

    else

        cout << "The smallest element is " << first << " and second "

            "Smallest element is " << second << endl; 

  
/ * Код водителя * /

int main() 

    int arr[] = {12, 13, 1, 10, 34, 1}; 

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

    print2Smallest(arr, n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для поиска самых маленьких и вторых самых маленьких элементов
#include <stdio.h>
#include <limits.h> /* For INT_MAX */

  

void print2Smallest(int arr[], int arr_size)

{

    int i, first, second;

  

    / * Должно быть как минимум два элемента * /

    if (arr_size < 2)

    {

        printf(" Invalid Input ");

        return;

    }

  

    first = second = INT_MAX;

    for (i = 0; i < arr_size ; i ++)

    {

        / * Если текущий элемент меньше первого

           затем обновите первый и второй * /

        if (arr[i] < first)

        {

            second = first;

            first = arr[i];

        }

  

        / * Если arr [i] находится между первым и вторым

           затем обновите второй * /

        else if (arr[i] < second && arr[i] != first)

            second = arr[i];

    }

    if (second == INT_MAX)

        printf("There is no second smallest element\n");

    else

        printf("The smallest element is %d and second "

               "Smallest element is %d\n", first, second);

}

  
/ * Программа драйвера для проверки вышеуказанной функции * /

int main()

{

    int arr[] = {12, 13, 1, 10, 34, 1};

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

    print2Smallest(arr, n);

    return 0;

}

Джава

// Java программа для поиска самых маленьких и вторых самых маленьких элементов

import java.io.*;

  

class SecondSmallest

{

    / * Функция для печати первого наименьшего и второго наименьшего

      элементы * /

    static void print2Smallest(int arr[])

    {

        int first, second, arr_size = arr.length;

  

        / * Должно быть как минимум два элемента * /

        if (arr_size < 2)

        {

            System.out.println(" Invalid Input ");

            return;

        }

  

        first = second = Integer.MAX_VALUE;

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

        {

            / * Если текущий элемент меньше первого

              затем обновите первый и второй * /

            if (arr[i] < first)

            {

                second = first;

                first = arr[i];

            }

  

            / * Если arr [i] находится между первым и вторым

               затем обновите второй * /

            else if (arr[i] < second && arr[i] != first)

                second = arr[i];

        }

        if (second == Integer.MAX_VALUE)

            System.out.println("There is no second" +

                               "smallest element");

        else

            System.out.println("The smallest element is " +

                               first + " and second Smallest" +

                               " element is " + second);

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main (String[] args)

    {

        int arr[] = {12, 13, 1, 10, 34, 1};

        print2Smallest(arr);

    }

}
/ * Этот код предоставлен Девешом Агравалом * /

питон

# Программа Python для поиска самых маленьких и вторых самых маленьких элементов

import sys

  

def print2Smallest(arr):

  

    # Должно быть как минимум два элемента

    arr_size = len(arr)

    if arr_size < 2:

        print "Invalid Input"

        return

  

    first = second = sys.maxint

    for i in range(0, arr_size):

  

        # Если текущий элемент меньше первого, то

        # обновить как первое, так и второе

        if arr[i] < first:

            second = first

            first = arr[i]

  

        # Если arr [i] находится между первым и вторым, то

        # обновить второе

        elif (arr[i] < second and arr[i] != first):

            second = arr[i];

  

    if (second == sys.maxint):

        print "No second smallest element"

    else:

        print 'The smallest element is',first,'and' \

              ' second smallest element is',second

  
# Функция драйвера для проверки вышеуказанной функции

arr = [12, 13, 1, 10, 34, 1]

print2Smallest(arr)

  
# Этот код предоставлен Девешом Агравалом

C #

// C # программа для поиска самых маленьких
// и вторые самые маленькие элементы

using System;

  

class GFG

{

      

    / * Функция для печати первого наименьшего

     и вторые самые маленькие элементы * /

    static void print2Smallest(int []arr)

    {

        int first, second, arr_size = arr.Length;

  

        / * Должно быть как минимум два элемента * /

        if (arr_size < 2)

        {

            Console.Write(" Invalid Input ");

            return;

        }

  

        first = second = int.MaxValue;

          

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

        {

            / * Если текущий элемент меньше первого

            затем обновите первый и второй * /

            if (arr[i] < first)

            {

                second = first;

                first = arr[i];

            }

  

            / * Если arr [i] находится между первым и вторым

            затем обновите второй * /

            else if (arr[i] < second && arr[i] != first)

                second = arr[i];

        }

        if (second == int.MaxValue)

            Console.Write("There is no second" +

                            "smallest element");

        else

            Console.Write("The smallest element is " +

                            first + " and second Smallest" +

                            " element is " + second);

    }

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void Main()

    {

        int []arr = {12, 13, 1, 10, 34, 1};

        print2Smallest(arr);

    

}

  
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для поиска самых маленьких и
// вторые самые маленькие элементы

  

function print2Smallest($arr, $arr_size)

{

    $INT_MAX = 2147483647;

      

    / * Там должно быть по крайней мере

       два элемента * /

    if ($arr_size < 2)

    {

        echo(" Invalid Input ");

        return;

    }

  

    $first = $second = $INT_MAX;

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

    {

          

        / * Если текущий элемент

           меньше первого

           обновить как первое, так и

           второй * /

        if ($arr[$i] < $first)

        {

            $second = $first;

            $first = $arr[$i];

        }

  

        / * Если arr [i] находится между

           первый и второй то

           обновить второе * /

        else if ($arr[$i] < $second && 

                 $arr[$i] != $first)

            $second = $arr[$i];

    }

    if ($second == $INT_MAX)

        echo("There is no second smallest element\n");

    else

        echo "The smallest element is ",$first

             ," and second Smallest element is "

                                     , $second;

}

  
// Код драйвера

$arr = array(12, 13, 1, 10, 34, 1);

$n = count($arr);

print2Smallest($arr, $n)

  
// Этот код предоставлен Smitha
?>


Выход :

The smallest element is 1 and second Smallest element is 10

Тот же подход можно использовать для поиска самых больших и вторых по величине элементов в массиве.

Сложность времени: O (n)

Связанная статья:
Минимальные и Вторые минимальные элементы с использованием минимальных сравнений

Пожалуйста, пишите комментарии, если вы обнаружите какую-либо ошибку в вышеуказанной программе / алгоритме или другие способы решения той же проблемы.

Рекомендуемые посты:

Найти самые маленькие и вторые самые маленькие элементы в массиве

0.00 (0%) 0 votes