C++程序 计算最大总和的对数
给定一个数组arr[],计算出满足 arr[i] + arr[j] 最大且 i < j 的所有数对 (arr[i], arr[j]) 的数量。
示例 :
输入:arr [] = {1, 1, 1, 2, 2, 2}
输出:3
方法1(Naive)
通过一个循环 i 从 0 到 n(也就是数组长度),再通过另外一个循环 j 从 i+1 到 n,来查找所有可能的数对 (i, j)。
// CPP program to count pairs with maximum sum.
#include <bits/stdc++.h>
using namespace std;
// function to find the number of maximum pair sums
int sum(int a[], int n)
{
// traverse through all the pairs
int maxSum = INT_MIN;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
maxSum = max(maxSum, a[i] + a[j]);
// traverse through all pairs and keep a count
// of the number of maximum pairs
int c = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] + a[j] == maxSum)
c++;
return c;
}
// driver program to test the above function
int main()
{
int array[] = { 1, 1, 1, 2, 2, 2 };
int n = sizeof(array) / sizeof(array[0]);
cout << sum(array, n);
return 0;
}
输出:
3
时间复杂度: O(n^2)
方法2(Efficient)
如果我们仔细观察,我们可以注意以下几点。
- 最大元素总是解决方案的一部分
- 如果最大元素出现不止一次,则结果为maxCount *(maxCount-1)/ 2。 我们基本上需要从maxCount( maxCount C 2 )中选择2个元素。
- 如果最大元素只出现一次,则结果等于第二大元素的计数。 我们可以将每个第二大和最大值配对形成一对。
// CPP程序用于计算最大和对的数量。
#include <bits/stdc++.h>
using namespace std;
// 查找最大对和的数量的函数
int sum(int a[], int n)
{
// 查找最大和第二大的元素,以及它们的出现次数。
int maxVal = a[0], maxCount = 1;
int secondMax = INT_MIN, secondMaxCount;
for (int i = 1; i < n; i++) {
if (a[i] == maxVal)
maxCount++;
else if (a[i] > maxVal) {
secondMax = maxVal;
secondMaxCount = maxCount;
maxVal = a[i];
maxCount = 1;
}
else if (a[i] == secondMax) {
secondMax = a[i];
secondMaxCount++;
}
else if (a[i] > secondMax) {
secondMax = a[i];
secondMaxCount = 1;
}
}
// 如果最大元素重复出现。
if (maxCount > 1)
return maxCount * (maxCount - 1) / 2;
// 如果最大元素只出现一次。
return secondMaxCount;
}
// 驱动程序来测试上面的函数
int main()
{
int array[] = { 1, 1, 1, 2, 2, 2, 3 };
int n = sizeof(array) / sizeof(array[0]);
cout << sum(array, n);
return 0;
}
输出结果:
3
时间复杂度: O(n)