C++程序 计算最大总和的对数

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)

如果我们仔细观察,我们可以注意以下几点。

  1. 最大元素总是解决方案的一部分
  2. 如果最大元素出现不止一次,则结果为maxCount *(maxCount-1)/ 2。 我们基本上需要从maxCount( maxCount C 2 )中选择2个元素。
  3. 如果最大元素只出现一次,则结果等于第二大元素的计数。 我们可以将每个第二大和最大值配对形成一对。
// 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)

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例