百度笔试题：高效计算数组重叠区间长度与捣乱分子对数

在本资源中，我们讨论了两个编程题目，分别来自百度的笔试题。 第一个问题是关于实现一个名为`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)。 在实际应用中，要确保内存使用合理，避免不必要的数据结构拷贝和内存分配，以满足限制条件。