在 vc++ 中组合两个向量的最佳方式
我正在寻找更好的逻辑来组合两个向量。
vector_A[id][mark1];
vector_B[id][mark2];
vector_A: id = [300 , 502, 401 , 900 , 800 ,700 , 250 , 001]
mark1 = [55 , 50 , 30 , 28 , 25 , 11 , 04 , 03]
vector_B: id = [800 , 005 , 502 , 925 ,025 ,300 , 52]
mark2 = [75, 60 , 50 ,35 , 30 , 25 , 04]
组合规则是如果在两个向量中找到相同的id，则添加mark1和mark2。如果不只是显示。
vector_combined: id = [800 , 300 , 502 , 005 , 925 , 401]
mark_combine = [100, 80 , 100 , 60 , 35 ,30]
请帮我提供一个最佳解决方案。
I am finding a better logic to combine 2 vectors.
vector_A[id][mark1];
vector_B[id][mark2];
vector_A: id = [300 , 502, 401 , 900 , 800 ,700 , 250 , 001]
mark1 = [55 , 50 , 30 , 28 , 25 , 11 , 04 , 03]
vector_B: id = [800 , 005 , 502 , 925 ,025 ,300 , 52]
mark2 = [75, 60 , 50 ,35 , 30 , 25 , 04]
combination rule is If same id find in two vectors add mark1 and mark2. If not just display.
vector_combined: id = [800 , 300 , 502 , 005 , 925 , 401]
mark_combine = [100, 80 , 100 , 60 , 35 ,30]
Please help me with a optimal solution.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
因此，我们很乐意为人们提供家庭作业问题的提示，只要他们已经坦率地承认该问题是家庭作业——就像您一样 :)
就目前情况而言，在
vector_A中查找特定元素的匹配项，您需要扫描vector_B中的每个元素。因此，如果vector_A中有 m 个元素，vector_B中有 n 个元素，则需要 O(mn) 时间才能找到所有匹配项——相当慢。假设我们对这两个向量进行排序，并相应地重新排序
mark1和mark2。您现在注意到的是，在vector_B中查找特定元素时，一旦找到太大的元素，您就可以停止 - 因为您知道所有后面的元素必须更大。这会节省一些时间。事实上，您可以更进一步，仅查看
vector_A和vector_B的第一个元素。我们分别称之为a和b。现在只能发生以下 3 种情况之一：a < b.。在这种情况下，我们可以得出结论，a不能出现在vector_B中的任何地方，因为所有后面的元素将至少与一样大b，它已经太大了。b不能出现在vector_A中的任何地方，因为后面的所有元素都至少与a一样大code>，已经太大了。a = b。在这种情况下，显然这个数字出现在两个向量中！请记住，排序只需要 O(nlog n) 时间，这应该会给您提供更快算法的重要提示。如果您需要更多帮助理解，请发表评论。
Here on SO we're happy to assist people with hints for homework questions, provided they have been up-front about acknowledging the question as homework -- as you have been :)
As things are now, to find a match for a particular element in
vector_A, you need to scan every element ofvector_B. So if there are m elements invector_Aand n elements invector_B, this will take O(mn) time to find all matches -- quite slow.Suppose we sort these two vectors, and reorder
mark1andmark2accordingly as well. What you now notice is that when looking for a particular element invector_B, you can stop as soon as you get to an element that is too large -- since you know that all later elements must be even larger. That will save some time.In fact you can go one step further and look at just the 1st element of
vector_Aandvector_B. Let's call theseaandbrespectively. Now only one of 3 cases can occur:a < b. In this case, we can conclude thatacannot appear anywhere invector_B, since all later elements will be at least as large asb, which is already too large.a > b. Similarly we can conclude thatbcannot appear anywhere invector_A, since all later elements will be at least as large asa, which is already too large.a = b. In that case, clearly this number appears in both vectors!Bearing in mind that sorting takes just O(nlog n) time, this should give you a big hint for a faster algorithm. If you need a bit more help understanding, leave a comment.
我不确定我是否正确理解您的问题...但是，您是否有机会寻找 std::set_intersection ？
该算法要求对您的范围进行排序。因此，对它们进行排序并将它们提供给
set_intersectionI am not sure if I understand your problem correctly... but, are you by any chance looking for std::set_intersection ?
The algorithm requires your ranges to be sorted. So, sort them and feed them to
set_intersection