นับคู่ที่มีค่าเฉลี่ยอยู่ในอาเรย์เดียวกันใน 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

คำอธิบาย − คู่ที่ค่าเฉลี่ยอยู่ใน arr[] คือ − (-1,5) ค่าเฉลี่ยคือ 2, (2,8) ค่าเฉลี่ยคือ 5 จำนวน=2

อินพุต − arr[] = {1,3,2,5,10,6}

เอาต์พุต − จำนวนคู่ที่มีค่าเฉลี่ยอยู่ในอาเรย์เดียวกัน คือ 3

คำอธิบาย − คู่ที่ค่าเฉลี่ยอยู่ใน arr[] คือ − (1,3) ค่าเฉลี่ย 2, (1,5) ค่าเฉลี่ย 3, (2,10) ค่าเฉลี่ย 6 จำนวน=3

แนวทางที่ใช้ในโปรแกรม

เราจะสร้างอาเรย์ความถี่สำหรับสมาชิกทั้งหมดของอาเรย์ ขนาดของอาเรย์ความถี่เป็นสองเท่าของอาเรย์เดิม เพราะอาจมีสมาชิกติดลบด้วย

ความถี่ของจำนวนติดลบจะเริ่มจากดัชนี 0 ถึง 1000 และความถี่ของจำนวนบวกจะเริ่มจากดัชนี 1000 ถึง 2000

สำหรับความถี่ที่ไม่เป็นศูนย์ ทำดังนี้ −

1. บวก (freq[i]) * (freq[i]-1)/2 เข้า count เพราะค่าเฉลี่ยของตัวเลขเดียวกันสองตัวคือตัวเลขนั้นเอง หากมี 5 ตัวเลข 2 ในอาเรย์ คู่อทั้งหมดจะเป็น (5*(5-1))/2=10
2. ถ้าความถี่ freq[i] ข้างต้นไม่เป็นศูนย์ เริ่มเดินทางสำหรับความถี่สลับกัน เนื่องจากตัวเลขติดกันมีค่าเฉลี่ยเป็นทศนิยมและจะไม่อยู่ในอาเรย์
3. ถ้า freq[j] พบว่ไม่เป็นศูนย์ และ freq[(i+j)/2] ก็ไม่เป็นศูนย์ด้วย แล้วบวก freq[i]*freq[j] เข้า count (เพราะตัวเลขแต่ละตัวจับคู่กับทุกตัวเลขอื่นได้)

• รับอาเรย์จำนวนเต็ม arr[]
• ฟังก์ชัน average_pair(arr, size) รับอาเรย์และขนาด คืนจำนวนคู่ที่ค่าเฉลี่ยของสมาชิกในคู่อยู่ในอาเรย์ arr[] ด้วย
• กำหนด count เริ่มต้น 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 เข้า count ตามเงื่อนไข 1
• ตอนนี้ arr_freq[i] ไม่เป็นศูนย์ เดินทางความถี่สลับกันทุกตัว
• คำนวณ temp_2 = arr_freq[(i + j) / 2]
• ถ้า temp_2 ไม่เป็นศูนย์ และ arr_freq[j] ไม่เป็นศูนย์ เงื่อนไข 3 ถูกต้อง อัปเดต count ด้วยผลคูณ (arr_freq[i] * arr_freq[j])
• ท้ายสุดของการวนซ้ำทั้งหมด count จะมีจำนวนคู่ดังกล่าวทั้งหมด
• คืน count

ตัวอย่างโค้ด C++

#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