เราได้รับอาร์เรย์ที่มีองค์ประกอบจำนวนเต็ม เป้าหมายคือการหาคู่ที่ไม่ซ้ำกันขององค์ประกอบของอาร์เรย์ที่คู่ของประเภท (arr[i],arr[j]) มีดัชนีเช่นที่ฉัน

ให้เราเข้าใจด้วยตัวอย่าง

ป้อนข้อมูล − arr[] ={1,2,3};

ผลผลิต − จำนวนคู่ที่ไม่ซ้ำ (arr[i], arr[j]) โดยที่ i

คำอธิบาย − เนื่องจากองค์ประกอบทั้งหมดมีเอกลักษณ์เฉพาะตัว คู่จะเป็น −

(1,2) - ( arr[0],arr[1] ) 0<1
(1,3) - ( arr[0], arr[2] ) 0<2
(2,3) - ( arr[1],arr[2] ) 1<2

ป้อนข้อมูล − arr[] ={ 4,4,3,2};

ผลผลิต − จำนวนคู่ที่ไม่ซ้ำ (arr[i], arr[j]) โดยที่ i

คำอธิบาย − เนื่องจากองค์ประกอบทั้งหมดมีเอกลักษณ์เฉพาะตัว คู่จะเป็น −

(4,4) - ( arr[0],arr[1] ) 0<1
(4,3) - ( arr[0], arr[2] ) 0<2
(4,2) - ( arr[0],arr[3] ) 0<3
(3,2) - ( arr[2],arr[3] ) 2<3

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

เราจะใช้สองวิธี วิธีไร้เดียงสาครั้งแรกโดยใช้ for loop เริ่มการสำรวจอาร์เรย์ arr[] โดยใช้ two for loops จาก i=0 ถึง i> se; ที่ขนาดท้ายของ 'se' จะเป็นจำนวนคู่ที่ไม่ซ้ำกับ i

• นำอาร์เรย์จำนวนเต็ม arr[] ที่มีองค์ประกอบจำนวนเต็มและความยาวเป็นขนาด

• ฟังก์ชัน unique_pair(int arr[], int size) รับอาร์เรย์และความยาวและส่งคืนจำนวนคู่ที่ไม่ซ้ำซึ่งในคู่ (arr[i],arr[j]) ดัชนี i

• ใช้ค่าเริ่มต้นนับเป็น 0

• ใช้เซต 'se' ที่มีคู่จำนวนเต็ม (set> se)

• เริ่มสำรวจ arr[] โดยใช้ two for loops จาก i=0 ถึง i<ขนาด-1 และ j=i+1 ถึง j<ขนาด

• สำหรับแต่ละคู่เสมอ i

• ในตอนท้ายของทั้งสองลูป ให้อัปเดต count=se.size()

• Count ตอนนี้มีจำนวนคู่ใน 'se' ( ทั้งหมดมีเอกลักษณ์เฉพาะตัว )

• ผลตอบแทนนับเป็นผลลัพธ์

แนวทางที่มีประสิทธิภาพ

ในแนวทางนี้ เราจะพบองค์ประกอบที่ไม่ซ้ำกันหลังจากแต่ละองค์ประกอบ arr[i] จะจับคู่กับองค์ประกอบที่แตกต่าง/ไม่ซ้ำกันจาก arr[ i+1 ถึง size-1 ] ดังนั้นหากมีองค์ประกอบเฉพาะ x หลัง arr[i] แล้ว arr[i] จะสร้างคู่ x ดังนั้นก่อนอื่นเราจะสร้างอาร์เรย์ที่ทำเครื่องหมายองค์ประกอบที่ไม่ซ้ำกันหลังจากดัชนี i จากนั้นเพิ่มจำนวนดังกล่าวเป็นรายบุคคลสำหรับคู่ที่ไม่ซ้ำทั้งหมด

• นำอาร์เรย์จำนวนเต็ม arr[] ที่มีองค์ประกอบจำนวนเต็มและความยาวเป็นขนาด

• ฟังก์ชัน unique_pair(int arr[], int size) รับอาร์เรย์และความยาวและส่งคืนจำนวนคู่ที่ไม่ซ้ำซึ่งในคู่ (arr[i],arr[j]) ดัชนี i

• ใช้ค่าเริ่มต้นนับเป็น 0

• นำตัวแปร temp มาตั้งค่าเป็น 0

• ใช้อาร์เรย์ขนาดความยาว arr_2[] และเริ่มต้น arr_2[size-1]=0 เนื่องจากองค์ประกอบสุดท้ายมีองค์ประกอบที่ไม่ซ้ำ 0 รายการหลังจากนั้น

• สร้างชุดจำนวนเต็มสองชุดตรวจสอบและยกเลิกการเลือก

• ข้ามอาร์เรย์จากองค์ประกอบสุดท้ายไปที่ first.i=size-1 ถึง i>=0 ค้นหา arr[i] ในชุดเช็ค

• หากไม่พบก็เป็นเอกลักษณ์ เพิ่ม temp (temp คือจำนวนองค์ประกอบที่ไม่ซ้ำหลังจาก arr[i] ) ตั้งค่า arr_2[i]=temp.

• อื่น arr_2[i]=temp. โดยไม่เพิ่มอุณหภูมิ

• ใส่ arr[i] เพื่อตั้งค่าการตรวจสอบ ตอนนี้จะไม่พิจารณาการเกิดขึ้นของ arr[i] ครั้งต่อไป

• ต่อจากนี้ไปสำหรับลูป arr_2[] ได้รับการอัปเดตแล้ว

• ตอนนี้สำรวจ arr[] จากดัชนี i=0 ถึง i

• เพิ่ม arr[i] เพื่อตั้งค่ายกเลิกการเลือก ตอนนี้การเกิดขึ้นครั้งต่อไปของ arr[i] จะไม่ได้รับการพิจารณา

• ในตอนท้ายนับจะมีคู่ที่ไม่ซ้ำกัน เช่น i

• ผลตอบแทนนับเป็นผลลัพธ์

ตัวอย่าง (แนวทางไร้เดียงสา)

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
   int count = 0;
   set<pair<int, int>> se;
   for(int i = 0; i < (size - 1); i++){
      for (int j = i + 1; j < size; j++){
         se.insert(make_pair(arr[i], arr[j]));
      }
   }
   count = se.size();
   return count;
}
int main(){
   int arr[] = { 4, 3, 1, 6, 7 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of unique pairs (arr[i], arr[j]) such that i & j are: 10

ตัวอย่าง (แนวทางที่มีประสิทธิภาพ)

#include<bits/stdc++.h>
using namespace std;
int unique_pair(int arr[], int size){
   int count = 0, temp = 0;
   int arr_2[size];
   arr_2[size-1] = 0;
   set<int> check, uncheck;
   for (int i = size - 1; i > 0; i--){
      auto set = check.find(arr[i]);
      if (set != check.end()){
         arr_2[i - 1] = temp;
      }
      else{
         arr_2[i - 1] = ++temp;
      }
      check.insert(arr[i]);
   }
   for (int i = 0; i < size - 1; i++){
      auto set = uncheck.find(arr[i]);
      if (set != uncheck.end()){
         continue;
      }
      count += arr_2[i];
      uncheck.insert(arr[i]);
   }
   return count;
}
int main(){
   int arr[] = { 4, 3, 1, 6, 7 };
   int size = sizeof(arr)/sizeof(arr[0]);
   cout<<"Count of unique pairs (arr[i], arr[j]) such that i < j are: "<<unique_pair(arr, size);
   return 0;
}

ผลลัพธ์

หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -

Count of unique pairs (arr[i], arr[j]) such that i < j are: 10