สืบค้นจำนวนองค์ประกอบอาร์เรย์ในช่วงที่มี Kth Bit Set โดยใช้ C++

ในบทความนี้เราจะพูดถึงปัญหาในการค้นหาจำนวนองค์ประกอบในช่วงที่กำหนดซึ่งมีชุดบิตที่ k ตัวอย่างเช่น -

อินพุต:arr[] ={ 4, 5, 7, 2 }ข้อความค้นหา 1:L =2, R =4, K =4Query 2:L =3, R =5, K =1Output :0 1 

 เราจะแก้ปัญหานี้ด้วยวิธีเดรัจฉาน และดูว่าวิธีนี้ใช้ได้กับข้อจำกัดที่สูงขึ้นหรือไม่ หากไม่เป็นเช่นนั้น เราก็พยายามคิดหาแนวทางใหม่ที่มีประสิทธิภาพ
 
แนวทางกำลังเดรัจฉาน
 

 ในแนวทางนี้ เราจะเพียงแค่ผ่านช่วงและตรวจสอบแต่ละองค์ประกอบว่าตั้งค่าบิต kth หรือไม่ ถ้าใช่ เราจะเพิ่มจำนวนขึ้น
 
ตัวอย่าง
 
#includeusing เนมสเปซ std;#define MAX_BITS 32bool Kset (int n, int k) { // เพื่อตรวจสอบว่ามีการตั้งค่าบิต kth หรือไม่หาก (n &(1 <<(k - 1) ))) คืนค่าจริง; คืนค่าเท็จ} แบบสอบถาม int (int L, int R, int K, int arr []) { จำนวน int =0; // ตัวนับเพื่อให้นับจำนวนที่มีอยู่ในช่วงสำหรับ (int i =L; i <=R; i++) { // สำรวจช่วง if (Kset(arr [i], K)) { count ++; } } จำนวนการส่งคืน;}int main() { int arr[] ={ 4, 5, 7, 2 }; // กำหนดอาร์เรย์ int n =sizeof(arr) / sizeof(arr[0]); // ขนาดของแบบสอบถาม int อาร์เรย์ของเรา[][3] ={ // กำหนด L, R และ k {2, 4, 4 }, { 3, 5, 1 } }; int q =sizeof(แบบสอบถาม) / sizeof(แบบสอบถาม[0]); // จำนวนข้อความค้นหาสำหรับ (int i =0; i  
ผลลัพธ์
 
01
 

 วิธีการข้างต้นมีความซับซ้อนของเวลาของ O(N*Q) โดยที่ N คือขนาดของอาร์เรย์ของเรา และ Q คือจำนวนการสืบค้นที่เราได้รับในขณะนี้ อย่างที่คุณเห็น แนวทางนี้ไม่เหมาะสำหรับข้อจำกัดที่สูงขึ้น เนื่องจากจะใช้เวลามากเกินไป ดังนั้นตอนนี้เราจะพยายามสร้างโปรแกรมของแนวทางที่มีประสิทธิภาพ
 
แนวทางที่มีประสิทธิภาพ
 

 ในแนวทางนี้ เราจะรักษาอาร์เรย์ผลรวมนำหน้า 2 มิติที่จะนับทุกบิตที่ใช้จนถึงแต่ละดัชนี จากนั้นเราสามารถคำนวณคำตอบในความซับซ้อน O(1)
 
ตัวอย่าง
 
#includeใช้เนมสเปซ std;#define บิต 32 // จำนวนของบิตซินต์ P[100000][บิต+1];bool Kset(int n, int k) { if (n &( 1 <<(k - 1))) คืนค่าจริง; return false;} void prefixArray (int n, int arr []) { // การสร้างอาร์เรย์คำนำหน้าสำหรับ (int i =0; i <=bits; i++) { P[0][i] =0; // การตั้งค่าทุกบิตเริ่มต้นนับ =0 } สำหรับ (int i =0; i  
ผลลัพธ์
 
23
 

 ขณะที่เรากำลังดูแลอาร์เรย์คำนำหน้าที่ช่วยเราค้นหาคำตอบใน O(1) ด้วยเหตุนี้ ความซับซ้อนของเวลาของเราจึงลดลงอย่างมากเป็น O(N) โดยที่ N คือขนาดของอาร์เรย์ที่เรากำหนดให้
 
คำอธิบายของโค้ดด้านบน
 

 ในโปรแกรมนี้ เรารักษาตัวนับคำนำหน้าสำหรับทุกดัชนีของอาร์เรย์ที่นับทุกบิตที่ใช้จนถึงดัชนี เราสร้างการนับนี้สำหรับอาร์เรย์ของเราในขณะนี้ เนื่องจากเรามีจำนวนคำนำหน้าของทุกบิตที่เก็บไว้กับเรา ดังนั้นสำหรับการนับบิตที่ kth เราจำเป็นต้องลบจำนวนคำนำหน้าของ kth บิตจนถึงดัชนี R ด้วยจำนวนคำนำหน้าของ kth บิตจนถึง L- 1 ดัชนีและนั่นคือคำตอบของเรา
 
บทสรุป
 

 ในบทความนี้ เราแก้ปัญหาเพื่อแก้ปัญหาการสืบค้นสำหรับจำนวนขององค์ประกอบอาร์เรย์ในช่วงด้วย Kth Bit Set นอกจากนี้เรายังได้เรียนรู้โปรแกรม C ++ สำหรับปัญหานี้และแนวทางที่สมบูรณ์ ( Normal และ มีประสิทธิภาพ ) โดยที่เราแก้ไขปัญหานี้ เราสามารถเขียนโปรแกรมเดียวกันในภาษาอื่น ๆ เช่น C, java, python และภาษาอื่น ๆ เราหวังว่าคุณจะพบว่าบทความนี้มีประโยชน์