C++：最快的方法來找到另一個陣列中的一個陣列的元素數

我有兩個數組，一個排序數組int b[]和其他未排序數組。有序數組由部分或全部未排序數組構成。現在有M個查詢。對於每個查詢值l和和r給出。在每個查詢中，我需要找到存在於b[]中的a[n]元素的數量。C++：最快的方法來找到另一個陣列中的一個陣列的元素數

對於如 -

N=5 ,M=2 
a= [2 5 1 2 3] 
b=[3 2 1] 
for each m: 
l=1 r=5 ->a[1]=1, a[5]=5 -> answer should be 3 as all elements of b i.e 1,2,3 are present in a 
l=2 r=4 ->a[2]=5 , a[4]=2 ->answer should be 2 as only 1 and 2 are there in b for given value of l and r for array.

如何找到不超過Ø（M * LOGN）時間複雜度的答案嗎？

注意： 數組不是必需的。也可以使用Vector，這有助於減少時間複雜性或更易於實現代碼。

來源

2016-12-03 tanmay_freak

這聽起來很像_homework_。對？不幸的是，SO不是代碼寫入服務。你到現在爲止嘗試了什麼？你的代碼面臨的實際問題是什麼？ – skypjack

@skypjack對不起，這不是一個家庭作業。這是使用DP解決問題的一部分。現在計算我在問題中需要計算的最終答案。那麼我試圖使用嵌套for循環，但時間限制超過。 –

不能從頭頂上想出很多..但.. ..是數組中唯一的元素嗎？你可以彈出找到的數組成員，避免稍後迭代它們，內循環應該在已排序的數組上以利用分支預測？ – Swift

嗯，我想你可以做這樣的事情

std::map<int,int> c; 
for(int i = 0;i<b.length.i++){ 
    c[b[i]] = 0; 
} 
for(int i = l; i<=r; i++){ 
    int number = a[i]; 
    c[number]++; 
} 
//Iterate through c with b index and get all number which different than 0. The left is for you

這樣做的目的是創造B的地圖保存索引然後同時遍歷一個你可以增加C值。因此，在此之後，您可以檢查C中的每個元素是否具有不同於零的值意味着A具有B的數量。如果C從零開始並且爲了獲得更好的性能而增加1，則可以使用數組而不是映射。如果使用數組，請確保檢查[i]是否可以拋出界限異常。

來源

2016-12-03 09:31:11

你能否請求循環回答？對於* M *查詢，這會給** O（M N）**的時間複雜度。我需要減少這個時間複雜性。 –

如果你真的想那麼快。只需創建一個矩陣[x] [y]，其中x等於左，y等於右。將所有結果解析到矩陣中，然後可以通過返回矩陣[l] [r]爲M查詢設置一個O（1）。 –

C++：最快的方法來找到另一個陣列中的一個陣列的元素數

回答

相關問題