นับคู่ที่มีค่าเฉลี่ยอยู่ในอาร์เรย์เดียวกันใน C++

เราได้รับอาร์เรย์ของจำนวนเต็มเพื่อให้แต่ละองค์ประกอบของอาร์เรย์อยู่ในช่วง [- 1,000,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) ค่าเฉลี่ยคือ 2, (2,8) เฉลี่ยคือ 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

สำหรับความถี่ที่ไม่ใช่ศูนย์ให้ทำสิ่งนี้ -

เพิ่ม (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 ถึง 1,000 และองค์ประกอบบวกในภายหลัง สำหรับสิ่งนี้ให้เพิ่ม N ลงในดัชนี
สำหรับแต่ละองค์ประกอบ arr[i] ให้อัปเดตอาร์เรย์ความถี่เป็น arr_freq[arr[i] + N]++;
ตอนนี้ สำรวจอาร์เรย์ความถี่จาก i=0 ถึง i
สำหรับการเพิ่มความถี่ที่ไม่ใช่ศูนย์แต่ละครั้ง (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<<"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