จำนวนลำดับย่อยที่มีองค์ประกอบที่แตกต่างกันสูงสุดใน C++

เราได้รับอาร์เรย์ arr[] ที่มีจำนวนเต็มเท่านั้น เป้าหมายคือการหาจำนวนลำดับของ arr[] เพื่อให้มีจำนวนองค์ประกอบที่แตกต่างกันมากที่สุด หากอาร์เรย์เป็น [ 4,1,2,3,4 ] สองส่วนรองจะเป็น [ 4,1,2,3 ] และ [ 1,2,3,4 ]

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

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

ผลผลิต − จำนวนย่อยที่มีองค์ประกอบต่างกันสูงสุดคือ − 4

คำอธิบาย − องค์ประกอบที่แตกต่างกันสูงสุดคือ 1,2,3,4 และ 5 Count คือ 5 ลำดับที่ตามมาจะเป็น -

[ 1,3,5,4,2 ], [ 3,5,4,2,1], [ 5,4,2,3,1 ], [ 1,5,4,2,3 ].

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

ผลผลิต − จำนวนย่อยที่มีองค์ประกอบต่างกันสูงสุดคือ − 1

คำอธิบาย − องค์ประกอบทั้งหมดมีความแตกต่างกัน จำนวนที่ตามมาจะเป็น 1

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

ในแนวทางนี้ เราจะพบลำดับย่อยโดยพิจารณาจากข้อเท็จจริงที่ว่าหากองค์ประกอบทั้งหมดแตกต่างกัน จำนวนลำดับรองคือ 1 ซึ่งเป็นตัวอาร์เรย์เอง ในกรณีที่มีองค์ประกอบที่ซ้ำกัน องค์ประกอบที่ทำซ้ำแต่ละรายการจะเป็นส่วนหนึ่งขององค์ประกอบที่ตามมาใหม่ ดังนั้นเราจะสร้าง unorderdered_map ของความถี่ขององค์ประกอบที่แตกต่างกัน จากนั้นสำหรับแต่ละความถี่คูณความถี่นั้นเพื่อนับ เมื่อสิ้นสุดการนับจะมีจำนวนความถี่ทั้งหมด

• รับอาร์เรย์จำนวนเต็ม arr[] เป็นอินพุต

• ฟังก์ชัน Max_distinct_subseq(int arr[], int size) ใช้อาร์เรย์และขนาดของอาร์เรย์ และส่งกลับจำนวนลำดับย่อยที่มีองค์ประกอบที่แตกต่างกันสูงสุด

• ใช้การนับเริ่มต้นเป็น 1 ราวกับว่าองค์ประกอบทั้งหมดมีความแตกต่างกัน จากนั้นอาร์เรย์เองก็เป็นลำดับรองที่มีองค์ประกอบที่แตกต่างกันสูงสุด

• สร้าง unordered_map แฮช; เพื่อเก็บความถี่ขององค์ประกอบที่แตกต่างกันทั้งหมด

• สำรวจอาร์เรย์โดยใช้ for loop และอัปเดตความถี่สำหรับแต่ละองค์ประกอบ arr[i] โดยใช้ hash[arr[i]]]++

• ตอนนี้สำรวจแฮชโดยใช้ for loop สำหรับแต่ละความถี่ it->second( it=iterator) คูณกับจำนวนก่อนหน้า เนื่องจากองค์ประกอบ x ในเวลาเดียวกันจะเป็นส่วนหนึ่งของ x ลำดับย่อยที่แตกต่างกัน

• เมื่อสิ้นสุดการนับจะมีจำนวนความถี่ทั้งหมด

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

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
int Max_distinct_subseq(int arr[], int size){
   int count = 1;
   unordered_map<int, int> hash;
   for (int i = 0; i < size; i++){
      hash[arr[i]]++;
   }
   for (auto it = hash.begin(); it != hash.end(); it++){
      count = count * (it->second);
   }
   return count;
}
int main(){
   int arr[] = { 3, 7, 3, 3, 1, 5, 6, 9 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Count of subsequences having maximum distinct elements are: "<<Max_distinct_subseq(arr, size);
   return 0;
}

ผลลัพธ์

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

Count of subsequences having maximum distinct elements are: 3