gpt4 book ai didi

c++ - 在 C++ 中计算有序集的并集

转载 作者:行者123 更新时间:2023-11-27 22:53:45 25 4
gpt4 key购买 nike

我想结合游程编码方案的三种变体(游程是累积的,因此是变体)。
让我们从其中两个开始:
第一个包含 bool 值列表,第二个包含计数器列表。假设第一个看起来如下:(值:该值的位置):

[(true:6), (false:10), (true:14), (false:20)]
// From 1 to 6, the value is true
// From 7 to 10, the value is false
// From 11 to 14, the value is true
// From 15 to 20, the value is false

第二个看起来如下(再次(值:该值的位置)):

[(1:4), (2:8), (4:16), (0:20)]
// From 1 to 4, the value is 1
// From 5 to 8, the value is 2
// From 9 to 16, the value is 4
// From 17 to 20, the value is 0

如您所见,两种情况下的位置略有不同:

Case 1 : [6, 10, 14, 20]
Case 2 : [4, 8, 16, 20]

我想通过计算它们的并集来组合这些“位置数组”:

[4, 6, 8, 10, 14, 16, 20]

一旦我有了这个,我就会从那里推导出新的方案:

[(true:4), (true:6), (false:8), (false:10), (true:14), (false:16), (false:20)]
[(1:4), (2:6), (2:8), (4:10), (4:14), (4:16), (0:20)]

我想知道:是否有任何 C++ 标准类型/类可以包含“数组”[6、10、14、20] 和 [4、8、16、20],计算它们的并集并对其进行排序?

谢谢
多米尼克

最佳答案

您需要使用 std::set_union 来自 <algorithm> .

我使用 std::vector<int>在这里,但它可以是任何模板类型。

#include <iostream>
#include <array>
#include <algorithm>

int main() {
std::vector<int> a{6, 10, 14, 20};
std::vector<int> b{4, 8, 16, 20};
std::vector<int> c;

std::set_union(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));
for(auto e: c) {
std::cout << e << ' ';
}
std::cout << '\n';
}

Here's the ideone

如果您只想维护两个 std::vector不介绍c ,您可以简单地附加 ba ,对数组进行排序,然后调用 std::uniquea .在 O(n)可能有一个聪明的方法来做到这一点,但这是天真的方法:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
std::vector<int> a{6, 10, 14, 20};
std::vector<int> b{4, 8, 16, 20};

a.insert(a.end(), b.begin(), b.end());

std::sort(a.begin(), a.end());
auto last = std::unique(a.begin(), a.end());
a.erase(last, a.end());

for(auto e: a) {
std::cout << e << ' ';
}
std::cout << '\n';
}

Here's the ideone

最后,你可以使用std::inplace_merge而不是 std::sort .在最坏的情况下它是 O(nlogn)喜欢std::sort , 但在最好的情况下是 O(n) .相当大的性能提升:

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
std::vector<int> a{6, 10, 14, 20};
std::vector<int> b{4, 8, 16, 20};

auto a_size = a.size();

a.insert(a.end(), b.begin(), b.end());

// merge point is where `a` and `b` meet: at the end of original `a`.
std::inplace_merge(a.begin(), a.begin() + a_size, a.end());

auto last = std::unique(a.begin(), a.end());
a.erase(last, a.end());

for(auto e: a) {
std::cout << e << ' ';
}
std::cout << '\n';
}

Here's the ideone

关于c++ - 在 C++ 中计算有序集的并集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/35131643/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com