C++实现计算最少添加数字次数以匹配两个数组元素

以下是解决此问题的C++代码： ```cpp #include <iostream> #include <algorithm> #include <vector> // 此函数用于计算最少添加数字的次数 int minAdditions(std::vector<int>& a, std::vector<int>& b) { int n = a.size(); int m = b.size(); // 对a数组和b数组进行排序，方便后续配对操作 std::sort(a.begin(), a.end()); std::sort(b.begin(), b.end()); int i = 0, j = 0; // 已匹配的元素数量 int matched = 0; while (i < n && j < m) { if (b[j] >= a[i]) { // 如果b[j] >= a[i]，说明可以匹配，将匹配数量加1 matched++; i++; j++; } else { // 如果b[j] < a[i]，b[j]无法匹配，尝试下一个b元素 j++; } } // 最少添加数字的次数为a数组长度减去已匹配的元素数量 return n - matched; } int main() { int n, m; std::cin >> n >> m; std::vector<int> a(n); std::vector<int> b(m); // 读取a数组的元素 for (int i = 0; i < n; i++) { std::cin >> a[i]; } // 读取b数组的元素 for (int i = 0; i < m; i++) { std::cin >> b[i]; } // 调用minAdditions函数计算最少添加数字的次数 int result = minAdditions(a, b); std::cout << result << std::endl; return 0; } ``` ### 代码解释 1. **排序操作**：对`a`数组和`b`数组进行排序，这样可以方便后续的匹配操作。 2. **匹配过程**：使用双指针`i`和`j`分别遍历`a`数组和`b`数组。如果`b[j] >= a[i]`，说明可以将`b[j]`和`a[i]`匹配，将匹配数量`matched`加1，并将`i`和`j`都向后移动一位；如果`b[j] < a[i]`，说明`b[j]`无法匹配，将`j`向后移动一位。 3. **计算结果**：最少添加数字的次数为`a`数组的长度减去已匹配的元素数量。 ### 复杂度分析 - **时间复杂度**：排序操作的时间复杂度为$O(n log n + m log m)$，匹配过程的时间复杂度为$O(n + m)$，因此总的时间复杂度为$O(n log n + m log m)$。 - **空间复杂度**：主要是存储`a`数组和`b`数组的空间，因此空间复杂度为$O(n + m)$。 ######[AI问答 | 714点数解答 | 2026-03-08 19:44:54]