เราได้รับอาร์เรย์ arr[] ที่มีองค์ประกอบจำนวนเต็ม เป้าหมายคือหาจำนวนคู่ที่สามารถสร้างได้จากองค์ประกอบของเซิร์ฟอาร์เรย์ของ arr[] โดยที่แต่ละเซิร์ฟอาร์เรย์มีเฉพาะองค์ประกอบที่แตกต่างกัน หากอาร์เรย์คือ [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] - คู่: (1,2)
[2,1] - คู่: (2,1)
[1,2,3] - คู่: (1,2), (2,3), (1,3)
รวมคู่: 5
แนวทางที่ใช้ในโปรแกรมด้านล่าง
- รับอาร์เรย์จำนวนเต็มเป็นอินพุต
- ฟังก์ชัน distinct_pairs(int arr[], int size) รับอาร์เรย์และคืนค่าจำนวนคู่ที่สร้างจากเซิร์ฟอาร์เรย์องค์ประกอบที่แตกต่างกัน
- ตั้งค่า count เริ่มต้นเป็น 0 ใช้ตัวแปร start=end=0
- ใช้ vector check(size, false) เพื่อทำเครื่องหมายองค์ประกอบในหน้าต่าง
- เริ่มลูป WHILE จนกว่า start จะน้อยกว่า size
- ภายในลูป เริ่มลูป WHILE อีกอันจนกว่า start น้อยกว่า size และ check[arr[start]] = 0 แล้วตั้ง count เป็น start - end และตั้ง check[arr[start]] เป็น true และเพิ่ม start ขึ้น 1
- เริ่มลูป WHILE จนกว่า end น้อยกว่า start และ start ไม่เท่ากับ size และ check[arr[start]] = true แล้วตั้ง check[arr[end]] = false และเพิ่ม end ขึ้น 1
- คืนค่า count
- พิมพ์ผลลัพธ์
ตัวอย่างโค้ด
#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
