我有以下任务:
- 编写具有头文件的函数**:long long CountSumS(vector & a,int s)
该函数将返回具有(a [i],a [j])的对的数目;i〈j; a [i]+ a [j]= s)示例:如果a =(8,2,3,8,7,5)且s = 10,则函数将返回3,这三对函数分别为(8,2)、(2,8)和(3,7)
我也在尝试高效地执行此操作,所以简单地每隔一个元素检查一次之后所有值的总和并不是我所寻找的解决方案。
我试着用一个无序的多重Map来解决这个问题,我得到了以下函数:
long long CountSumS(vector<int>& v, int sum)
{
int cnt = 0;
typedef unordered_multimap<int, int>::iterator iter;
unordered_multimap<int, int> m;
for (int i = 0; i < v.size(); i++)
m.insert(make_pair(v[i], i));
for (int i = 0; i < v.size(); i++)
{
int x = sum - v[i];
//the needed value to make the sum
pair<iter, iter> result = m.equal_range(x);
int count = distance(result.first, result.second);
if (count != 0)
{
for (auto iter = result.first; iter != result.second; iter ++) //iterates through the values
{
if (iter->second > i)
cnt++;
/*else
iter = m.erase(iter);*/
}
}
}
return cnt;
它解决这个问题的效率很低,因为毕竟它只是检查了所有带有某个键的元素,所以我想到的解决方案是删除map中所有值小于"i"的元素,因为它意味着元素已经被传递到向量中了,所以我不能用它来求和。这是我试图擦除迭代器上的值的方法,但是当我试图运行代码(image)(https://i.stack.imgur.com/Nl3SI.png)时,我得到了一个错误,我想知道是什么导致了这个错误。
我感谢所有的投入,对一个更好的aproach为一个更容易的解决方案,这只是第一件事,我能想到的,并试图实施。
2条答案
按热度按时间zzlelutf1#
在
iter = m.erase(iter)
之后使用iter ++
可能导致迭代器溢出。在每次迭代中只执行其中一个。
syqv5f0l2#
如果只想返回(a[i],a[j])对的个数;i〈j; a[i] + a[j] = s),你可以使用不同的方法。不要创建一个std::unordered_multimap〈int,int〉容器,即一个哈希表,并在检查满足 predicate 的元素对之前将所有的元素对插入其中,而是应该使用另一个std::vector容器,其中的元素是排序的。因此,如果你有一个元素a[i],你需要找到满足等价a[i] + a[j] = s的其他元素a[j],你将在该范围内迭代该容器。关于效率,我可以建议你做以下优化:使用一个copy ctor将给定向量中的元素转移到你的向量中,这样你就避免了将来的重新分配,你的代码也更清晰;使用标准算法对向量进行排序,例如std::sort()。因此,您可以利用二进制搜索算法来查找每个元素a[i]的元素数,因此总和不会超出给定范围。
算法如下:初始化变量,比如说,正确地作为一个.size()- 1并计数为0,以存储总和位于[L,U]范围内的对的数目。迭代直到right大于0,并找到与a[right]的总和大于或等于L的元素的起始索引。然后,查找在a[right]之前的元素的结束索引,该元素与a[right]的和小于或等于U。如果结束大于等于开始,然后将(end-start + 1)加到表示其与当前元素的和位于范围[L,U]上的元素的数目的计数上,然后向右递减。
此外,您还应该纠正一个小错误,但这并不重要:函数自变量
std::vector<int>&
应该是常量引用const std::vector<int>&
,因为它所包含的元素从未被修改。