计算 C++ 中同一数组中存在的平均值的对

  • Z时代
  • 2024-01-10
  • 分类：综合

我们得到一个整数数组，数组的每个元素都在 [- 1000,1000] 范围内。目标是找到数组的元素对，使得它们的平均值也存在于该数组中。如果数组是 arr[]= [1,2,3,4]。那么对将是 (1,3) 和 (2,4)，因为 1,3 的平均值是 2，2,4 的平均值是 3，并且 2 和 3 都存在于数组中。计数将为 2。

让我们通过例子来理解。

输入- arr[]= { -1,2,5,-3,8,10 }

输出- 同一数组中平均存在的对数为 - 2

说明- 对使得它们的平均值出现在 arr[] 中是 - (-1,5) avg 是 2, (2,8) avg 是 5. Count=2

输入- arr[] = {1,3,2,5,10,6}

输出- 同一数组中平均存在的对数为 - 3

说明- 对使得它们的平均值出现在 arr[] 中是 - (1,3) avg 为 2，(1,5) avg 为 3，(2,10) avg 为 6。Count=3。

下面程序中使用的方法如下

我们将首先为数组的所有元素制作一个频率数组。频率数组的大小是原始数组大小的两倍，因为也可能存在负元素。

负数出现的频率将从索引 0 开始到索引 1000。正数出现的频率将从索引 1000 开始到 2000。

对于每个非零频率执行此操作 -

  1. 将 (freq[i]) * (freq[i]-1)/2 添加到计数中，因为两个相同数字的平均值就是数字本身。如果数组中有 5 个 2。那么总对数将是 (5*(5-1))/2=10。

  2. 如果上述 freq[i] 不为零，则开始遍历替代频率，因为连续数字的平均值是浮点数，并且不会出现在数组中。

  3. 如果找到非零的 freq[j] 并且 freq[ (i+j)/2 ] 也非零。然后将 freq[i]*freq[j] 添加到count( as each number can pair with every other number ).

  • 取一个整数数组 arr[]

  • 函数average_pair(arr, size)获取数组及其大小并返回对的计数，使得对中元素的平均值也存在于数组 arr[] 中。

  • 取初始计数为0，初始化N=1000。

  • 计算频率数组的长度为 size_2=2*N+1 （范围 [-1000 到 1000]

  • 最初用 0 初始化频率数组。

  • 填充频率数组，使得负元素的频率从 0 到 1000，然后是正元素。为此，将 N 添加到索引中。

  • 对于每个元素 arr[i] 更新频率数组为 arr_freq[arr[i] + N]++；

  • 现在遍历频率数组，从 i=0 到 i<size_2。

  • 对于每个非零频率添加 (freq[i]) * (freq[i]-1)/2 以根据条件 1 进行计数。

  • 现在 arr_freq[i] 非零，遍历每个交替频率。

  • 将 temp_2 计算为 arr_freq[(i + j) / 2]。

  • 现在，如果 temp_2 非零且 arr_freq[j] 非零，则满足条件 3。用产品更新计数 (arr_freq[i] * arr_freq[j]);

  • 在所有迭代结束后，计数将具有此类对的总数。

  • 返回计数作为结果。

示例

#include <bits/stdc++.h>
using namespace std;
int average_pair(int arr[], int size_1){
   int count = 0;
   int N = 1000;
   int size_2 = (2 * N) + 1;
   int arr_freq[size_2] = { 0 };
   for (int i = 0; i < size_1; i++){
      int temp = arr[i];
      arr_freq[temp + N]++;
   }
   for (int i = 0; i < size_2; i++){
      if (arr_freq[i] > 0){
         int check = (arr_freq[i]) * (arr_freq[i] - 1);
         count += check / 2;
         for (int j = i + 2; j < 2001; j += 2){
            int temp_2 = arr_freq[(i + j) / 2];
            if (arr_freq[j] > 0 && temp_2 > 0){
               count += (arr_freq[i] * arr_freq[j]);
            }
         }
      }
   }
   return count;
}
int main(){
   int arr[] = { 2, 3, 1, 8, 9, 10 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"同一数组中平均存在的对数为： "<<average_pair(arr, size);
   return 0;
}
输出结果

如果我们运行上面的代码，它将生成以下输出 -

同一数组中平均存在的对数为： 2

以上是 计算 C++ 中同一数组中存在的平均值的对 的全部内容， 来源链接： utcz.com/z/338849.html

回到顶部