在本资源中，我们讨论了两个编程题目，分别来自百度的笔试题。
第一个问题是关于实现一个名为`foo`的函数，该函数接受两个无符号整数数组`a1`和`a2`，以及它们的长度`al1`和`al2`。这两个数组表示的是数字区间，且数组长度均为偶数。任务是找到这两个数组重叠部分的长度。例如，对于给定的数组：
- a1: [0, 1, 3, 6, 10, 20]
- a2: [0, 1, 20, 50, 4, 5]
重叠部分是 [0, 1] 和 [4, 5]，长度为 2。函数要求高效计算并返回重叠区间的长度，同时注意数组长度不超过100万，且可能存在多重重叠。设计思路应考虑如何遍历和比较数组，避免冗余计算，以优化空间和时间复杂度。
第二个问题是处理一个身高排序问题。给定一个整数序列，表示人的身高，需要找出那些身高不符合正常顺序（前面的人身高小于或等于后面的人）的“捣乱分子”对的数量。例如，对于序列 [176, 178, 180, 170, 171]，捣乱分子对有多个。解决方案应涉及有效的遍历和比较算法，可能使用哈希或其他数据结构来快速查找冲突对。输入限制为每行最大数字个数100000，数字最长为6位，要求输出捣乱分子对的总数，而不仅仅是具体的对。
对于这两个问题，编写高效的代码时，关键在于：
1. 对于`foo`函数，可以使用集合（Set）数据结构来存储区间，快速查找交集，然后计算交集元素数量。
2. 对于身高问题，可以使用排序后比较，或者使用双指针法（从两端开始对比，记录当前未匹配的最小值和最大值）来检测捣乱分子。
代码实现和复杂度分析：
由于篇幅限制，这里提供核心代码片段：
```c++
// foo 函数实现
size_t foo(unsigned int*a1, size_t al1, unsigned int*a2, size_t al2) {
std::set<std::pair<unsigned int, unsigned int>> set1(a1, a1 + al1 / 2);
std::set<std::pair<unsigned int, unsigned int>> set2(a2, a2 + al2 / 2);
size_t overlap = 0;
for (auto& p : set1) {
auto it = set2.lower_bound({p.first, INT_MAX});
if (it != set2.end() && it->first <= p.second) {
overlap += it->second - it->first + 1;
set2.erase(it);
}
}
return overlap * 2; // 由于区间是成对出现的，所以长度翻倍
}
// 身高问题实现
int findDistractors(int* heights, size_t length) {
sort(heights, heights + length);
int mismatches = 0;
for (size_t i = 0; i < length - 1; ++i) {
if (heights[i] >= heights[i + 1]) {
mismatches += i; // 记录每个捣乱分子对的起始位置
}
}
return mismatches;
}
```
时间复杂度分析：
- `foo`函数：使用集合查找的时间复杂度为O(al1 + al2)，总时间复杂度约为O(al1 + al2)。
- 身高问题：排序的时间复杂度为O(n log n)，遍历查找捣乱分子对的时间复杂度为O(n)，总时间复杂度约为O(n log n)。
在实际应用中，要确保内存使用合理，避免不必要的数据结构拷贝和内存分配，以满足限制条件。
我的内容管理
展开
