C++程序 大小为两个组之间的最大差异

C++程序 大小为两个组之间的最大差异

给定一个由元素偶数组成的数组,使用这些数组元素形成2个组,使最高和组与最低和组之间的差异最大。

注: 一个元素只能是一个组的一部分,并且必须是至少一个组的一部分。

例子:

Input : arr[] = {1, 4, 9, 6} 
Output : 10 
Groups formed will be (1, 4) and (6, 9),
the difference between highest sum group 
(6, 9) i.e 15 and lowest sum group (1, 4) 
i.e 5 is 10.

Input : arr[] = {6, 7, 1, 11} 
Output : 11 
Groups formed will be (1, 6) and (7, 11),
the difference between highest sum group 
(7, 11) i.e 18 and lowest sum group (1, 6) 
i.e 7 is 11.

简单的方法: 我们可以通过对所有可能的组合进行枚举,并检查最高和组与最低和组之间的差异来解决此问题。将形成n *(n-1)/ 2个这样的组(nC2)。

时间复杂度:O(n^3),因为需要O(n^2)生成组,并且需要n次迭代检查每个组的总体总和,因此总体需要O(n^3)时间。

高效的方法: 我们可以使用贪婪方法。将整个数组排序,我们的结果是最后两个元素的总和减去第一个两个元素的总和。

// CPP program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
 
ll CalculateMax(ll arr[], int n)
{
    // Sorting the whole array.
    sort(arr, arr + n);
    
    int min_sum = arr[0] + arr[1];
    int max_sum = arr[n-1] + arr[n-2];
 
    return abs(max_sum - min_sum);
}
 
// Driver code
int main()
{
    ll arr[] = { 6, 7, 1, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << CalculateMax(arr, n) << endl;
    return 0;
}  

输出

11

时间复杂度: O(n * log n)

空间复杂度: O(1),因为没有使用额外的空间。

进一步优化:

不使用排序,可以在线性时间内找到两个最大值和两个最小值,并将时间复杂度降低到O(n)。

下面是上述方法的代码。

// C++ program to find minimum difference
// between groups of highest and lowest
// sums.
#include <bits/stdc++.h>
using namespace std;
 
int CalculateMax(int arr[], int n)
{
     
    int first_min = *min_element(arr, arr + n);;
    int second_min = INT_MAX;
    for(int i = 0; i < n ; i ++)
    {
        // If arr[i] is 不等于第一个最小值,则执行以下操作
        if (arr[i] != first_min)
            second_min = min(arr[i],second_min);
    }
     
    int first_max = *max_element(arr, arr + n);
    int second_max = INT_MIN;
    for (int i = 0; i < n ; i ++)
    {
        // If arr[i] is not equal to first max
        if (arr[i] != first_max)
            second_max = max(arr[i],second_max);
    }
     
    return abs(first_max+second_max-first_min-second_min);
     
}
 
// Driver code
int main()
{
    int arr[] = { 6, 7, 1, 11 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << CalculateMax(arr, n) << endl;
    return 0;
}
 
// This code is contributed by Aman Kumar```  

输出

11

时间复杂度: O(N)

辅助空间: O(1)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例