Рубрики

Минимальная пара продуктов массив целых положительных чисел

Дан массив натуральных чисел. Нам необходимо написать программу для вывода минимального произведения из любых двух чисел данного массива.

Примеры:

Input : 11 8 5 7 5 100
Output : 25 
Explanation : The minimum product of any 
two numbers will be 5 * 5 = 25.

Input : 198 76 544 123 154 675 
Output : 7448
Explanation : The minimum product of any 
two numbers will be 76 * 123 = 7448.

Простой подход. Простым подходом будет запуск двух вложенных циклов для генерации всех возможных пар элементов и отслеживания минимального продукта.
Сложность времени: O (n * n)
Вспомогательное пространство: O (1)

Лучший подход: эффективный подход будет состоять в том, чтобы сначала отсортировать указанный массив и вывести произведение первых двух чисел, сортировка займет O (n log n). Ответ будет тогда [0] * a [1]
Сложность времени: O (n * log (n))
Вспомогательное пространство: O (1)

Лучший подход . Идея заключается в линейном обходе заданного массива и отслеживании минимум двух элементов. Наконец, верните произведение двух минимальных элементов.

Ниже приведена реализация вышеуказанного подхода.

C ++

// C ++ программа для расчета минимума
// произведение пары
#include <bits/stdc++.h>

using namespace std;

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

int printMinimumProduct(int arr[], int n)

{

    // Инициализируем первое и второе

    // минимумы. Предполагается, что

    // массив состоит как минимум из двух элементов.

    int first_min = min(arr[0], arr[1]);

    int second_min = max(arr[0], arr[1]);

  

    // Обходим оставшийся массив и сохраняем

    // трек двух минимальных элементов (Примечание

    // что два минимальных элемента могут

    // быть таким же, если появляется минимальный элемент

    // больше чем единожды)

    // больше чем единожды)

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

    {

       if (arr[i] < first_min)

       {

          second_min = first_min;

          first_min = arr[i];

       }

       else if (arr[i] < second_min)

          second_min = arr[i];

    }

  

    return first_min * second_min;

}

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

int main()

{

    int a[] = { 11, 8 , 5 , 7 , 5 , 100 };

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

    cout << printMinimumProduct(a,n);

    return 0;

}

Джава

// Java программа для расчета минимума
// произведение пары

import java.util.*;

  

class GFG {

      

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

    // пары

    static int printMinimumProduct(int arr[], int n)

    {

        // Инициализируем первое и второе

        // минимумы. Предполагается, что

        // массив состоит как минимум из двух элементов.

        int first_min = Math.min(arr[0], arr[1]);

        int second_min = Math.max(arr[0], arr[1]);

       

        // Обходим оставшийся массив и сохраняем

        // трек двух минимальных элементов (Примечание

        // что два минимальных элемента могут

        // быть таким же, если появляется минимальный элемент

        // больше чем единожды)

        // больше чем единожды)

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

        {

           if (arr[i] < first_min)

           {

              second_min = first_min;

              first_min = arr[i];

           }

           else if (arr[i] < second_min)

              second_min = arr[i];

        }

       

        return first_min * second_min;

    }

      

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

    public static void main(String[] args) 

    {

        int a[] = { 11, 8 , 5 , 7 , 5 , 100 };

        int n = a.length;

        System.out.print(printMinimumProduct(a,n));

       

    }

}

  
// Этот код предоставлен Арнавом Кр. Мандал.

python3

# Python программа для
# рассчитать минимум
# произведение пары

  
# Функция для расчета
# минимальный продукт
№ пары

def printMinimumProduct(arr,n):

  

    # Инициализировать первый и второй

    # минимумов. Предполагается, что

    # массив состоит как минимум из двух элементов.

    first_min = min(arr[0], arr[1])

    second_min = max(arr[0], arr[1])

   

    # Пройти оставшийся массив и сохранить

    # дорожка из двух минимальных элементов (Примечание

    # что два минимальных элемента могут

    # быть таким же, если появляется минимальный элемент

    # больше чем единожды)

    # больше чем единожды)

    for i in range(2,n):

      

         if (arr[i] < first_min):

         

            second_min = first_min

            first_min = arr[i]

         

         elif (arr[i] < second_min):

            second_min = arr[i]

      

    return first_min * second_min

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

  

a= [ 11, 8 , 5 , 7 , 5 , 100 ]

n = len(a)

  

print(printMinimumProduct(a,n))

  
# Этот код добавлен
# Анант Агарвал.

C #

// C # программа для расчета минимума
// произведение пары

using System;

  

class GFG {

      

    // Функция для расчета минимума

    // произведение пары

    static int printMinimumProduct(int []arr,

                                       int n)

    {

          

        // Инициализируем первое и второе

        // минимумы. Предполагается, что

        // в массиве есть как минимум два

        // элементы.

        int first_min = Math.Min(arr[0],

                                    arr[1]);

                                      

        int second_min = Math.Max(arr[0],

                                    arr[1]);

      

        // Обходим оставшийся массив и

        // отслеживаем два минимума

        // элементы (обратите внимание, что два

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

        // если появляется минимальный элемент

        // больше чем единожды)

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

        {

            if (arr[i] < first_min)

            {

                second_min = first_min;

                first_min = arr[i];

            }

            else if (arr[i] < second_min)

                second_min = arr[i];

        }

      

        return first_min * second_min;

    }

      

    / * Программа драйвера для тестирования выше

    функция * /

    public static void Main() 

    {

        int []a = { 11, 8 , 5 , 7 ,

                            5 , 100 };

        int n = a.Length;

          

        Console.WriteLine(

            printMinimumProduct(a, n));

    }

}

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

PHP

<?php
// PHP программа для расчета минимума
// произведение пары

  
// Функция для расчета минимума
// произведение пары

function printMinimumProduct($arr, $n)

{

      

    // Инициализируем первое и второе

    // минимумы. Предполагается, что

    // массив состоит как минимум из двух элементов.

    $first_min = min($arr[0], $arr[1]);

    $second_min = max($arr[0], $arr[1]);

  

    // Обходим оставшийся массив и сохраняем

    // трек двух минимальных элементов (Примечание

    // что два минимальных элемента могут

    // быть таким же, если появляется минимальный элемент

    // больше чем единожды)

    // больше чем единожды)

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

    {

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

        {

            $second_min = $first_min;

            $first_min = $arr[$i];

        }

        else if ($arr[$i] < $second_min)

            $second_min = $arr[$i];

    }

  

    return $first_min * $second_min;

}

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

$a = array(11, 8 , 5 , 7 , 5 , 100);

$n = sizeof($a);

echo(printMinimumProduct($a, $n));

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


Выход:

25

Сложность времени: O (n)
Вспомогательное пространство: O (1)

Эта статья предоставлена Раджа Викрамадитья . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

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

Минимальная пара продуктов массив целых положительных чисел

0.00 (0%) 0 votes