資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 查詢區間內第 K 位設定的陣列元素個數
在本文中，我們將討論一個問題，即查詢給定範圍內具有第 k 位設定的元素數量，例如 -
Input : arr[] = { 4, 5, 7, 2 }
Query 1: L = 2, R = 4, K = 4
Query 2: L = 3, R = 5, K = 1
Output :
0
1我們將透過蠻力方法解決這個問題，並看看這種方法是否適用於更高的約束。如果不是，那麼我們嘗試思考一種新的有效方法。
蠻力方法
在這種方法中，我們將簡單地遍歷該範圍並檢查每個元素的第 k 位是否已設定，如果是，則增加計數。
示例
#include<bits/stdc++.h>
using namespace std;
#define MAX_BITS 32
bool Kset(int n, int k) { // to check if kth bit is set
if (n & (1 << (k - 1)))
return true;
return false;
}
int query(int L, int R, int K, int arr[]) {
int count = 0; // counter to keep count of number present in the range
for (int i = L; i <= R; i++) { // traversing the range
if (Kset(arr[i], K)) {
count++;
}
}
return count;
}
int main() {
int arr[] = { 4, 5, 7, 2 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of our array
int queries[][3] = { // given L, R and k
{ 2, 4, 4 },
{ 3, 5, 1 }
};
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K, arr) << "\n";
}
return 0;
}輸出
0 1
上述方法的時間複雜度為 O(N*Q)，其中 N 是陣列的大小，Q 是我們給定的查詢數量；如您所見，這種方法不適用於更高的約束，因為它將花費太多時間，因此現在我們將嘗試編寫一個高效方法的程式。
高效方法
在這種方法中，我們將維護一個二維字首和陣列，該陣列將保留每個索引之前使用的每個位的計數，然後我們可以在 O(1) 的複雜度內計算答案。
示例
#include<bits/stdc++.h>
using namespace std;
#define bits 32 // number of bits
int 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[]) { // building the prefix array
for (int i = 0; i <= bits; i++) {
P[0][i] = 0; // setting every bits initial count = 0
}
for (int i = 0; i < n; i++) {
for (int j = 1; j <= bits; j++) {
bool flag = Kset(arr[i], j);
if (i) // we add previous count to the latest count(0)
P[i][j] = P[i - 1][j];
if (flag) { // if jth bit is set so we increase the count
P[i][j]++;
}
}
}
}
int query(int L, int R, int K) {
if (L) // if L not equal to 0 then we return the prefix at R subtracted with prefix at L-1
return P[R][K] - P[L - 1][K];
else
return P[R][K];
}
int main() {
int arr[] = { 8, 9, 1, 3 }; // given array
int n = sizeof(arr) / sizeof(arr[0]); // size of given array
int queries[][3] = {
{ 1, 3, 4 },
{ 2, 4, 1 }
};
prefixArray(n, arr); // calling the function to create prefix array
int q = sizeof(queries) / sizeof(queries[0]); // number of queries
for (int i = 0; i < q; i++) {
int L = queries[i][0] - 1;
int R = queries[i][1] - 1;
int K = queries[i][2];
cout << query(L, R, K) << "\n";
}
return 0;
}輸出
2 3
由於我們正在維護字首陣列，這有助於我們在 O(1) 中找到答案，因此透過此操作，我們的時間複雜度大大降低到 O(N)，其中 N 是我們給定陣列的大小。
上述程式碼的解釋
在此程式中，我們為陣列的每個索引維護一個字首計數器，該計數器計算直到該索引為止使用的每個位。我們現在為我們的陣列構建此計數，因為我們已經儲存了每個位的數量字首，所以對於第 k 位計數，我們需要用第 k 位到 R 索引的字首計數減去第 k 位到 L-1 索引的字首計數，這就是我們的答案。
結論
在本文中，我們解決了一個問題，即解決查詢區間內第 K 位設定的陣列元素數量。我們還學習了此問題的 C++ 程式以及解決此問題的完整方法（普通方法和高效方法）。我們可以在其他語言（如 C、Java、Python 和其他語言）中編寫相同的程式。我們希望您發現本文有所幫助。
更新於：2021 年 11 月 26 日
248 次檢視
廣告