เราได้รับอาร์เรย์ของ สมมติว่า arr[] ของค่าจำนวนเต็มของขนาดใดๆ ตามลำดับ และภารกิจคือการคำนวณจำนวนคู่ที่แตกต่างกันที่มีอยู่ในอาร์เรย์ที่กำหนดซึ่งมีผลรวมอยู่ในอาร์เรย์เดียวกันด้วย
อาร์เรย์ประเภทโครงสร้างข้อมูลที่สามารถจัดเก็บคอลเล็กชันแบบต่อเนื่องที่มีขนาดคงที่ขององค์ประกอบประเภทเดียวกัน อาร์เรย์ใช้เพื่อจัดเก็บชุดข้อมูล แต่มักจะมีประโยชน์มากกว่าที่จะคิดว่าอาร์เรย์เป็นชุดของตัวแปรประเภทเดียวกัน
ข้อควรจำ
-
คู่จะถูกนับครั้งเดียวด้วยองค์ประกอบเดียวกันโดยไม่คำนึงถึงคำสั่งของพวกเขา ตัวอย่างเช่น (3,2) และ (2,3) จะนับเป็น 1
-
หากมีตัวเลขเกิดขึ้นหลายครั้งในอาร์เรย์ จะถูกพิจารณาสองครั้งพอดีเพื่อสร้างคู่เดียว ตัวอย่างเช่น หากอาร์เรย์มีองค์ประกอบเป็น {2, 2, 2, 2} คู่ก็จะเป็น (2,2) และจะถูกนับเป็น 1
ตัวอย่าง
Input − int arr = {6, 4, 10, 14}
Output − count is 2 คำอธิบาย − คู่ที่มีผลรวมในอาร์เรย์คือ (6,4) และ (10,4) ดังนั้นการนับเป็น 2
Input − int arr = {6, 6, 6 ,6, 6, 13}
Output − count is 0 คำอธิบาย - ไม่มีคู่ในอาร์เรย์ที่มีผลรวมในอาร์เรย์เดียวกัน นับเป็น 0
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
สร้างอาร์เรย์ สมมุติว่า arr[]
-
คำนวณความยาวของอาร์เรย์โดยใช้ฟังก์ชัน length() ที่จะคืนค่าจำนวนเต็มตามองค์ประกอบในอาร์เรย์
-
ใช้ตัวแปรชั่วคราวที่จะเก็บจำนวนองค์ประกอบ
-
สร้างตัวแปรประเภทแผนที่ สมมุติว่า mp
-
เริ่มวนรอบสำหรับ i ถึง 0 และฉันน้อยกว่าขนาดของอาร์เรย์
-
สร้างแมปอื่นของตัวแปรประเภทคู่ สมมุติว่าพาร์
-
เริ่มวนรอบสำหรับ i ถึง 0 และฉันน้อยกว่าขนาดของอาร์เรย์
-
ภายในลูป เริ่มลูปใหม่ด้วย j ถึง i+1 และ j น้อยกว่าขนาดของอาร์เรย์
-
ภายในลูป ตรวจสอบว่า mp[arr[i]+arr[j]]> 0 AND pr[{arr[i], arr[j] }] =0 แล้วเพิ่มจำนวนขึ้น 1
-
เพิ่มพาร์[{ arr[i], arr[j] }] โดย 1
-
เพิ่มพาร์[{ arr[j], arr[i] }] โดย 1
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#include <iostream>
#include <map>
using namespace std;
// Returns number of pairs in ar[0..n-1] with
// sum equal to 'sum'
int countpairs(int ar[], int n){
// Store counts of all elements in map m
// to find pair (ar[i], sum-ar[i])
// because (ar[i]) + (sum - ar[i]) = sum
map<int, int> mymap;
for (int i = 0; i < n; i++){
mymap[ar[i]]++;
}
// To remove duplicate items we use result map
map<pair<int, int>, int> p;
int result = 0;
// Considering all pairs
for (int i = 0; i < n; i++){
for (int j = i + 1; j < n; j++){
// If sum of current pair exists
if (mymap[ar[i] + ar[j]] > 0 && p[{ ar[i], ar[j] }] ==0){
result++;
}
// Inserting the current pair both ways to avoid
// duplicates.
p[{ ar[i], ar[j] }]++;
p[{ ar[j], ar[i] }]++;
}
}
return result;
}
// main function
int main(){
int ar[] = { 6, 4, 10, 14 };
int n = sizeof(ar) / sizeof(ar[0]);
cout << "count is "<<countpairs(ar, n);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น เราจะได้ผลลัพธ์ดังต่อไปนี้ -
count is 2
