資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中統計平均數也在同一陣列中的對數
給定一個整數陣列，其中陣列的每個元素都在範圍 [-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
說明 − 滿足條件的對為 − (-1, 5) 平均數為 2，(2, 8) 平均數為 5。計數 = 2
輸入 − arr[] = {1, 3, 2, 5, 10, 6}
輸出 − 平均數也在同一陣列中的對的計數為 − 3
說明 − 滿足條件的對為 − (1, 3) 平均數為 2，(1, 5) 平均數為 3，(2, 10) 平均數為 6。計數 = 3。
下面程式中使用的的方法如下
我們首先為陣列的所有元素建立一個頻率陣列。頻率陣列的大小是原始陣列的兩倍，因為也可能存在負元素。
負數的頻率將從索引 0 到索引 1000 開始。正數的頻率將從索引 1000 到 2000 開始。
對於每個非零頻率，執行以下操作：
將 (freq[i]) * (freq[i]-1)/2 加到計數中，因為兩個相同數字的平均數就是數字本身。如果陣列中有 5 個 2。那麼對的總數將為 (5*(5-1))/2=10。
如果上面的 freq[i] 非零，則開始遍歷交替頻率，因為連續數字的平均數是浮點數，並且不會出現在陣列中。
如果找到非零的 freq[j] 並且 freq[ (i+j)/2 ] 也非零。則將 freq[i]*freq[j] 加到計數中（因為每個數字都可以與其他每個數字配對）。
取一個整數陣列 arr[]
函式 average_pair(arr, size) 獲取陣列及其大小，並返回滿足條件的對的計數，即對中元素的平均數也在陣列 arr[] 中。
將初始計數設為 0，並將 N 初始化為 1000。
計算頻率陣列的長度為 size_2=2*N+1（對於範圍 [-1000 到 1000]）
最初將頻率陣列初始化為 0。
填充頻率陣列，使得負元素的頻率從 0 到 1000，正元素的頻率從 1000 之後開始。為此，將 N 加到索引中。
對於每個元素 arr[i]，更新頻率陣列為 arr_freq[arr[i] + N]++;
現在遍歷從 i=0 到 i<size_2 的頻率陣列。
對於每個非零頻率，根據條件 1 將 (freq[i]) * (freq[i]-1)/2 加到計數中。
現在由於 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<<"Count of pairs with average present in the same array are: "<<average_pair(arr, size);
return 0;
}輸出
如果我們執行以上程式碼，它將生成以下輸出：
Count of pairs with average present in the same array are: 2
223 次檢視
