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++：最快的方法来找到另一个阵列中的一个阵列的元素数

回答

相关问题