从整型向量中搜索整型向量的最佳算法
我是一个算法新手，我正在尝试找出(在内存效率和速度方面)最好的方法来找出整数的向量(样本向量)是否存在于整数的向量(人口向量)中。我将用一个例子来说明这个问题。
A={1,2,3,4,5,6,7,8}，这些是立方体的顶点。可以由它形成的六个面是{1,2,3,4}，{5,6,7,8}，{1,2,6,5}，{2,3,7,6}，{3,4,8,7} {4,1,8,5}
现在B={3,4,8,7}。所以我必须找出在人口向量的多少个A向量中是否存在B？(人口向量由几个A组成。)
我使用了一个哈希函数，将其B的值与A的6个向量进行比较，并对人口向量的所有向量运行一个循环。有没有更好的方法呢？
回答 1
Stack Overflow用户
发布于 2018-06-15 17:55:43
在向量中，Find是线性的。
2个vector<int>的==重载使用std::distance进行工作，如here所述。
因此，只需使用惯用的std::find
//vvint is the vector of vector of ints, vint is the vector of ints to be found
auto it = find (vvint.begin(), vvint.end(), vint);
if (it != vvint.end())
//found
else
//not found哈希函数不起作用，因为它们可能会产生冲突，除非您仔细检查相等，否则无法保证查找的有效性。这意味着2个或更多个4个整数的向量可以具有相同的散列，如您的示例所示。因此，您可能会通过散列找到对应关系，但实际向量有所不同。(但是，您可以创建一个散列函数，将包含4个整数的向量的一个子域统一映射为该子域中每个元素的唯一散列。)无论如何，这需要额外的unordered_map增加空间复杂性，以及增加插入和删除的复杂性。
当您定义一个有效的比较器并保持向量的排序时，Binary search是可能的，但对于向量是不可行的。为了做到这一点，重载<，然后查找将变成对数，但插入和删除需要查找每个查找，以找到添加或删除的位置，然后还可能触发多个元素的大小调整或移位，从而降低性能。
另外，向量的要点是它们不会排序。
这就是其他结构存在的原因，比如set
https://stackoverflow.com/questions/50873046
复制相似问题
腾讯云开发者
