C++ 数组距离求解 - 代码详解与优化

\u003cp\u003e\u003cstrong\u003e题目描述\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e给定两个分别为 n 和 m 的数组 x[] 和 y[]。从 x 中任意取出一个元素 x[i]，然后从 y 中任取一个元素 y[j]，他们的差的绝对值为 |x[i] - y[i]|，一共有 n × m 对这样的差值，其中最小的值称为数组的距离。\u003c/p\u003e\n\u003cp\u003e请你写一个程序求出数组的距离。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e输入\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e输入第一行两个整数 n, m (1 ≤ n, m ≤ 106)。\u003c/p\u003e\n\u003cp\u003e接下来一行输入 n 个整数表示数组 x。\u003c/p\u003e\n\u003cp\u003e接下来一行输入 m 个整数表示数组 y。\u003c/p\u003e\n\u003cp\u003e输入的数组元素绝对值小于等于 108。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e输出\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e输出一行一个整数表示两个数组的距离。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e样例输入\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e3 4\u003c/p\u003e\n\u003cp\u003e1 2 3\u003c/p\u003e\n\u003cp\u003e4 5 6 7\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e样例输出\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e1\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e样例解释\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e数组 x 和数组 y 的距离最小为 1，对应的元素为 2 和 3。\u003c/p\u003e\n\u003cp\u003e\u003cstrong\u003e代码实现 (C++)\u003c/strong\u003e\u003c/p\u003e\n\u003cpre\u003e\u003ccode\u003e#include \u003ciostream\u003e\n#include \u003calgorithm\u003e\nusing namespace std;\n\nint main() {\n int n, m;\n cin \u003e\u003e n \u003e\u003e m;\n int x[n], y[m];\n for (int i = 0; i \u003c n; i++) {\n cin \u003e\u003e x[i];\n }\n for (int i = 0; i \u003c m; i++) {\n cin \u003e\u003e y[i];\n }\n sort(x, x + n);\n sort(y, y + m);\n int min_distance = abs(x[0] - y[0]);\n for (int i = 0; i \u003c n; i++) {\n for (int j = 0; j \u003c m; j++) {\n min_distance = min(min_distance, abs(x[i] - y[j]));\n }\n }\n cout \u003c\u003c min_distance \u003c\u003c endl;\n return 0;\n}\n\u003c/code\u003e\u003c/pre\u003e\n\u003cp\u003e\u003cstrong\u003e优化建议\u003c/strong\u003e\u003c/p\u003e\n\u003cp\u003e1. 使用二分查找优化：由于数组已经排序，可以利用二分查找来寻找最接近的元素，从而减少时间复杂度。\u003c/p\u003e\n\u003cp\u003e2. 使用指针优化：可以利用指针来遍历数组，减少数组元素访问的时间消耗。\u003c/p\u003e\n\u003cp\u003e本篇文章仅供参考，如有任何问题或需要进一步优化，欢迎留言讨论。\u003c/p\u003e