C++程序计算最小正整数数组两个数的乘积

给定一个正整数数组。让我们编写一个程序来打印给定数组中任意两个数字的最小乘积。

例子：

输入：11 8 5 7 5 100
输出：25 
说明：任何两个数字的最小乘积为5 * 5 = 25。

输入：198 76 544 123 154 675 
输出：7448
说明：任何两个数字的最小乘积是76 * 123 = 7448。

简单方法： 一个简单的方法是运行两个嵌套循环以生成所有可能的元素对，并跟踪最小乘积。

时间复杂度：O(n ^ 2)

辅助空间：O(1)

更好的方法： 一个高效的方法是首先对给定数组进行排序，并打印出前两个数字的乘积，排序将花费O(n log n) 的时间。答案将是a[0] * a[1]。

// C++ program to calculate minimum
// product of a pair
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum product
// of pair
int printMinimumProduct(int arr[], int n)
{
    //Sort the array
    sort(arr,arr+n);
     
    // Returning the product of first two numbers
    return arr[0] * arr[1];
}
 
// Driver program to test above function
int main()
{
    int a[] = { 11, 8 , 5 , 7 , 5 , 100 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << printMinimumProduct(a,n);
    return 0;
}
 
// This code is contributed by Pushpesh Raj```

输出

时间复杂度：O(n log(n))

辅助空间：O(1)

最佳方法： 这个想法是线性遍历给定的数组并跟踪最小的两个元素。最后返回两个最小元素的乘积。

下面是上述方法的实现。

// C++ program to calculate minimum
// product of a pair
#include <bits/stdc++.h>
using namespace std;
 
// Function to calculate minimum product
// of pair
int printMinimumProduct(int arr[], int n)
{
    // Initialize first and second
    // minimums. It is assumed that the
    // array has at least two elements.
    int first_min = min(arr[0], arr[1]);
    int second_min = max(arr[0], arr[1]);
 
    // Traverse remaining array and keep
    // track of two minimum elements (Note
    // that the two minimum elements may
    // be same if minimum element appears
    // more than once)
    // more than once)
    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;
}
 
// Driver program to test above function
int main()
{
    int a[] = { 11, 8 , 5 , 7 , 5 , 100 };
    int n = sizeof(a) / sizeof(a[0]);
    cout << printMinimumProduct(a,n);
    return 0;
}

输出

时间复杂度：O(n)

辅助空间：O(1)