เราได้รับอาร์เรย์ arr[] ที่มีองค์ประกอบจำนวนเต็ม เป้าหมายคือการหาจำนวนคู่ที่สามารถเกิดขึ้นได้จากองค์ประกอบของอาร์เรย์ย่อยของ arr[] ซึ่งแต่ละ subarray มีองค์ประกอบที่แตกต่างกันเท่านั้น หากอาร์เรย์เป็น [ 1,2,2,3,3 ] ดังนั้นอาร์เรย์ย่อยที่มีองค์ประกอบที่แตกต่างกันเท่านั้นจะเป็น [ 1,2 ] และ [ 2,3 ] และคู่จะเป็น (1,2) และ (2,3) ดังนั้นการนับคู่คือ 2
ให้เราเข้าใจด้วยตัวอย่าง
ป้อนข้อมูล − arr[] ={1,2,5,3 }
ผลผลิต − จำนวนคู่ที่เกิดจากอาร์เรย์ย่อยขององค์ประกอบที่แตกต่างกันคือ − 6
คำอธิบาย − อาร์เรย์ย่อยที่มีองค์ประกอบต่างกัน ได้แก่ [ 1,2,5, 3] คู่ที่เป็นไปได้ (1,2) (1,3) (1,5), (2,5), (2,3), (5,3)
รวม 6 คู่
ป้อนข้อมูล − arr[] ={1,2,1,2,3}
ผลผลิต − จำนวนคู่ที่เกิดจากอาร์เรย์ย่อยขององค์ประกอบที่แตกต่างกันคือ − 5
คำอธิบาย − อาร์เรย์ย่อยที่มีองค์ประกอบต่างกันคือ −
[1,2] - pairs: (1,2) [2,1] - pairs: (2,1) [1,2,3] - pairs : (1,2), (2,3), (1,3) Total pairs : 5
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
-
ใช้อาร์เรย์จำนวนเต็มเป็นอินพุต
-
ฟังก์ชัน different_pairs(int arr[], int size) รับอาร์เรย์และส่งกลับคู่ Count ที่เกิดจากอาร์เรย์ย่อยขององค์ประกอบที่แตกต่างกัน
-
นับเริ่มต้นเป็น 0 ใช้ตัวแปร start=end=0
-
ตรวจสอบเวกเตอร์ (ขนาด เท็จ) เพื่อทำเครื่องหมายองค์ประกอบในหน้าต่าง
-
เริ่มวนรอบในขณะที่เริ่มน้อยกว่าขนาด
-
ภายในลูป ให้เริ่มลูปอื่นในขณะที่เริ่มน้อยกว่าขนาด และ check[arr[star]] =0 จากนั้นตั้งค่า count เป็น start - end และตั้งค่า check[arr[start]] เป็นจริง และเพิ่มการเริ่มต้น 1
-
เริ่มวนรอบในขณะที่สิ้นสุดน้อยกว่าเริ่มต้นและการเริ่มต้นไม่เท่ากับขนาด AND check[arr[start]] =true จากนั้นตั้งค่า check[arr[end]] =false และเพิ่มจุดสิ้นสุดด้วย 1
-
คืนจำนวน
-
พิมพ์ผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int distinct_pairs(int arr[], int size){
int count = 0;
int start = 0;
int end = 0;
vector<bool> check(size, false);
while (start < size){
while (start < size && !check[arr[start]]){
count += (start - end);
check[arr[start]] = true;
start++;
}
while (end < start && (start != size && check[arr[start]])){
check[arr[end]] = false;
end++;
}
}
return count;
}
int main(){
int arr[] = {5, 1, 8, 2, 1, 7, 9, 1};
int size = sizeof(arr) / sizeof(arr[0]);
cout<<"Count of pairs formed by distinct element sub-arrays are: "<< distinct_pairs(arr, size);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count of pairs formed by distinct element sub-arrays are: 17
