C++ 题解：求两个数组的距离

{ "title": "C++ 题解：求两个数组的距离", "description": "本题解提供了使用 C++ 语言求解两个数组距离的思路和代码实现，通过排序和双指针的方式高效地找到两个数组中元素差的最小值。", "keywords": "C++, 数组距离, 题解, 排序, 双指针, 最小值, 代码实现", "content": ""【题目描述】\n两个分别为n\n和m\n的数组x[]\n和y[]\n。从x\n中任意取出一个元素x[i]\n，然后从y\n中任取一个元素y[j]\n，他们的差的绝对值为∣x[i]−y[i]∣\n，一共有n×m\n 对这样的差值，其中最小的值称为数组的距离。\n\n请你写一个程序求出数组的距离。\n\n【输入】\n输入第一行两个整数n,m\n(1≤n,m≤106\n)。\n\n接下来一行输入 n\n个整数表示数组 x\n。\n\n接下来一行输入 m\n 个整数表示数组 y\n。\n\n输入的数组元素绝对值小于等于 108\n。\n\n【输出】\n输出一行一个整数表示两个数组的距离。\n\n【样例输入】\n3 4\n1 2 3\n4 5 6 7\n\n【样例输出】\n1\n\n【样例输入】\n2 2\n-1 0\n1 2\n\n【样例输出】\n0\n\n【解题思路】\n题目要求取两个数组中任意一个元素，使得它们的差的绝对值最小。这个问题可以转化为，在两个数组中分别找到一个元素，使得它们的差的绝对值最小。我们可以对两个数组分别进行排序，然后使用双指针的方式进行比较。初始时，两个指针分别指向两个数组的第一个元素，然后比较它们的差的绝对值，更新最小值。如果第一个指针指向的元素小于第二个指针指向的元素，则将第一个指针向后移动一位；反之，将第二个指针向后移动一位。一直进行下去，直到其中一个指针到达数组的末尾。最后得到的最小值就是数组的距离。\n\n【代码实现】\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\n#include <climits>\nusing namespace std;\n\nint main() {\n int n, m;\n cin >> n >> m;\n vector<int> x(n);\n vector<int> y(m);\n for (int i = 0; i < n; ++i) {\n cin >> x[i];\n }\n for (int i = 0; i < m; ++i) {\n cin >> y[i];\n }\n sort(x.begin(), x.end());\n sort(y.begin(), y.end());\n int i = 0, j = 0;\n int minDistance = INT_MAX;\n while (i < n && j < m) {\n minDistance = min(minDistance, abs(x[i] - y[j]));\n if (x[i] < y[j]) {\n ++i;\n } else {\n ++j;\n }\n }\n cout << minDistance << endl;\n return 0;\n}\n"\n}