首頁 > 後端開發 > C++ > 使用C++編寫程式碼,找出具有位元或值大於或等於K的子數組的數量

使用C++編寫程式碼,找出具有位元或值大於或等於K的子數組的數量

WBOY
發布: 2023-08-27 15:17:06
轉載
1092 人瀏覽過

使用C++編寫程式碼,找出具有位元或值大於或等於K的子數組的數量

在本文中,我們將簡要說明如何在 C 中求解位元 OR>=K 的子陣列的數量。所以我們有一個陣列 arr[] 和一個整數 K,我們必須找到 OR(位元或)大於或等於 K 的子陣列的數量。所以這是給定問題的範例-

Input: arr[] = {1, 2, 3} K = 3
Output: 4

Bitwise OR of sub-arrays:
{1} = 1
{1, 2} = 3
{1, 2, 3} = 3
{2} = 2
{2, 3} = 3
{3} = 3
4 sub-arrays have bitwise OR ≥ 3
Input: arr[] = {3, 4, 5} K = 6
Output: 2
登入後複製

尋找解決方案的方法

現在我們將使用兩種不同的方法來使用C 來解決問題-

暴力破解

在這種方法中,我們只是要遍歷所有可以形成的子數組並檢查OR 是否大於或等於K。如果是,那麼我們將增加我們的答案。

範例

#include <bits/stdc++.h>
using namespace std;
int main(){
    int arr[] = {1, 2, 3}; // given array.
    int k = 3;
    int size = sizeof(arr) / sizeof(int); // the size of our array.
    int answer = 0; // the counter variable.
    for(int i = 0; i < size; i++){
        int bitwise = 0; // the variable that we compare to k.
        for(int j = i; j < size; j++){ // all the subarrays starting from i.
            bitwise = bitwise | arr[j];
            if(bitwise >= k) // if bitwise >= k increment answer.
               answer++;
        }
    }
    cout << answer << "\n";
    return 0;
}
登入後複製

輸出

4
登入後複製
登入後複製

這種方法非常簡單,但它有其缺陷,因為這種方法對於較高的限制不太好,對於較高的約束,它會花費太多時間,因為這種方法的時間複雜度是O(N *N),其中N 是給定數組的大小,因此現在我們將採用一種有效的方法。

高效方法

在這種方法中,我們將使用OR 運算子的一些屬性,即即使我們添加更多數字,它也不會減少,因此如果我們從i 到j 得到一個子數組,其OR 大於或等於K,那麼每個包含範圍{i,j 的子數組} 將具有大於K 的OR,我們正在利用此屬性並改進我們的程式碼。

範例

#include <bits/stdc++.h>
#define N 1000
using namespace std;
int t[4*N];
void build(int* a, int v, int start, int end){ // segment tree building
    if(start == end){
       t[v] = a[start];
       return;
    }
    int mid = (start + end)/2;
    build(a, 2 * v, start, mid);
    build(a, 2 * v + 1, mid + 1, end);
    t[v] = t[2 * v] | t[2 * v + 1];
}
int query(int v, int tl, int tr, int l, int r){ // for processing our queries or subarrays.
    if (l > r)
       return 0;
    if(tl == l && tr == r)
       return t[v];
    int tm = (tl + tr)/2;
    int q1 = query(2*v, tl, tm, l, min(tm, r));
    int q2 = query((2*v)+1, tm+1, tr, max(tm+1, l), r);
    return q1 | q2;
}
int main(){
    int arr[] = {1, 2, 3}; // given array.
    int k = 3;
    int size = sizeof(arr) / sizeof(arr[0]); // the size of our array.
    int answer = 0; // the counter variable.
    build(arr, 1, 0, size - 1); // building segment tree.
    for(int i = 0; i < size; i++){
        int start = i, end = size-1;
        int ind = INT_MAX;
        while(start <= end){ // binary search
            int mid = (start + end) / 2;
            if(query(1, 0, size-1, i, mid) >= k){ // checking subarray.
               ind = min(mid, ind);
               end = mid - 1;
            }
            else
               start = mid + 1;
        }
        if(ind != INT_MAX) // if ind is changed then increment the answer.
            answer += size - ind;
    }
    cout << answer << "\n";
    return 0;
}
登入後複製

輸出

4
登入後複製
登入後複製

在這個方法中,我們使用二分搜尋和線段樹,這有助於將時間複雜度從O( N*N) 降低到O(Nlog(N)),這非常好的。現在,與前一個程式不同,該程式還可以適用於更大的約束。

結論

在本文中,我們解決了一個問題,以查找具有OR >= K 的子數組的數量使用二分搜尋和線段樹,時間複雜度為O(nlog(n))。我們也學習了解決這個問題的C 程序以及解決這個問題的完整方法(正常且有效率)。我們可以用其他語言像是C、java、python等語言來寫同樣的程式。希望這篇文章對您有幫助。

以上是使用C++編寫程式碼,找出具有位元或值大於或等於K的子數組的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章!

來源:tutorialspoint.com
本網站聲明
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn
最新問題
熱門教學
更多>
最新下載
更多>
網站特效
網站源碼
網站素材
前端模板