Trong bài viết này, chúng ta sẽ thảo luận về vấn đề tìm số phần tử có trong phạm vi đã cho có tập bit thứ k, chẳng hạn -
Đầu vào:arr [] ={4, 5, 7, 2} Truy vấn 1:L =2, R =4, K =4 Truy vấn 2:L =3, R =5, K =1 Đầu ra:0 1
Chúng tôi sẽ giải quyết vấn đề này bằng cách tiếp cận bạo lực và xem liệu cách tiếp cận này có thể hoạt động đối với các hạn chế cao hơn hay không. Nếu không, chúng tôi cố gắng nghĩ ra một cách tiếp cận hiệu quả mới.
Phương pháp tiếp cận vũ phu
Trong cách tiếp cận này, chúng tôi chỉ đơn giản là sẽ xem xét phạm vi và kiểm tra từng phần tử xem liệu bit thứ k của nó có được đặt hay không, nếu có, thì chúng tôi sẽ tăng số lượng.
Ví dụ
#include using namespace std; #define MAX_BITS 32bool Kset (int n, int k) {// để kiểm tra xem bit thứ k có được đặt không nếu (n &(1 <<(k - 1 ))) trả về true; return false;} int query (int L, int R, int K, int arr []) {int count =0; // bộ đếm để giữ số lượng có mặt trong phạm vi for (int i =L; i <=R; i ++) {// duyệt qua phạm vi if (Kset (arr [i], K)) {count ++; }} return count;} int main () {int arr [] ={4, 5, 7, 2}; // mảng đã cho int n =sizeof (arr) / sizeof (arr [0]); // kích thước mảng của chúng ta int queries [] [3] ={// cho trước L, R và k {2, 4, 4}, {3, 5, 1}}; int q =sizeof (truy vấn) / sizeof (truy vấn [0]); // số lượng truy vấn for (int i =0; i Đầu ra
01
Cách tiếp cận trên có độ phức tạp thời gian là O (N * Q) trong đó N là kích thước mảng của chúng ta và Q là số lượng truy vấn mà chúng ta được đưa ra bây giờ; như bạn có thể thấy, cách tiếp cận này không phù hợp với các ràng buộc cao hơn vì nó sẽ mất quá nhiều thời gian, vì vậy bây giờ chúng tôi sẽ cố gắng tạo ra một chương trình tiếp cận hiệu quả.
Phương pháp tiếp cận hiệu quả
Trong cách tiếp cận này, chúng tôi sẽ duy trì một mảng tổng tiền tố 2-D sẽ giữ số lượng từng bit được sử dụng cho đến mỗi chỉ mục và sau đó chúng tôi có thể tính toán câu trả lời theo độ phức tạp O (1).
Ví dụ
#include using namespace std; #define bits 32 // số bitint P [100000] [bits + 1]; bool Kset (int n, int k) {if (n &( 1 <<(k - 1))) return true; return false;} void prefixArray (int n, int arr []) {// xây dựng mảng tiền tố for (int i =0; i <=bits; i ++) {P [0] [i] =0; // thiết lập mọi bit đếm ban đầu =0} for (int i =0; i Đầu ra
23
Vì chúng tôi đang duy trì mảng tiền tố giúp chúng tôi tìm ra câu trả lời trong O (1) Vì vậy, bằng cách này, độ phức tạp về thời gian của chúng tôi giảm đáng kể xuống còn O (N), trong đó N là kích thước của mảng đã cho của chúng tôi.
Giải thích về đoạn mã trên
Trong chương trình này, chúng tôi duy trì một bộ đếm tiền tố cho mọi chỉ mục của mảng đếm từng bit được sử dụng cho đến chỉ mục. Chúng tôi xây dựng số đếm này cho mảng của chúng tôi ngay bây giờ vì chúng tôi có số tiền tố của mỗi bit được lưu trữ bên mình, vì vậy đối với số bit thứ k, chúng tôi cần trừ số tiền tố của bit thứ k cho đến chỉ mục R với số tiền tố của bit thứ k cho đến L- 1 chỉ mục và đó là câu trả lời của chúng tôi.
Kết luận
Trong bài viết này, chúng tôi giải quyết một vấn đề để giải quyết các Truy vấn cho số phần tử mảng trong một phạm vi với Tập bit thứ K. Chúng tôi cũng đã học chương trình C ++ cho vấn đề này và cách tiếp cận hoàn chỉnh (Bình thường và hiệu quả) mà chúng tôi đã giải quyết vấn đề này. Chúng tôi có thể viết cùng một chương trình bằng các ngôn ngữ khác như C, java, python và các ngôn ngữ khác. Chúng tôi hy vọng bạn thấy bài viết này hữu ích.