使用 BFS 查找与给定整数集距离最小的整数点
在此问题中，我们将从数组中给出的点中找到距离任何给定点最近的 K 个点。
要找到距离给定点最近的点，如果数组中不存在该元素，我们可以对数组的每个元素取 nums[p] + 1 或 nums[p] -1。如果我们需要更多点，我们可以取 nums[p] + 2 或 nums[p] – 2 个点，依此类推。
问题陈述
我们给出了一个包含 N 个正整数和负整数的 nums[] 数组。数组的每个点在二维空间中表示为 {nums[p], 0}。我们还给出了整数 K。我们需要找到总共 K 个点，以最小化每个点与其最近点的距离，该点存在于 nums[] 数组中。
示例
输入
nums[] = {1, 3, 5}; K = 3
输出
0, 2, 4
解释
这里，0 最接近 1。2 和 4 最接近 3。
输入
nums[] = {2, 3, 5, 7, -10, 12}, K = 5;
输出
1, 4, 6, 8, -11
解释
1 最接近 2。
4 最接近 3。
6 和 8 最接近 7。
-11 最接近 -10。
输入
nums[] = {7, 8, 9, 10, 12, 11}; K = 6;
输出
6, 13, 5, 14, 4, 15
解释
当数组中已经存在 nums[p] 元素时，我们需要取 nums[p] + 2，依此类推。
方法
在此方法中，我们将使用映射来跟踪原始数组元素和其他最近的元素。此外，我们将继续将最近的元素插入队列。之后，如果我们需要更多元素，我们可以将最近的元素与上一个最近的元素进行比较，以最小化距离。
算法
步骤 1 - 定义"num_map"映射和"que"队列。此外，定义"res"列表以存储 K 个最近的元素。
步骤 2 - 遍历数组元素并将元素插入到映射和队列中。
步骤 3 - 使用 while 循环进行 K 次迭代。
步骤 3.1 - 从队列中弹出第一个元素，并将其存储在"temp"变量中。
步骤 3.2 - 如果未访问 temp -1，并且 K 大于 0，则将 temp - 1 插入到映射和队列中。另外，将 temp - 1 推送到 res 列表中，并将 K 减少 1。
步骤 3.3 - 如果未访问 temp + 1，并且 K 大于 0，则将 temp + 1 插入到 map、queue 和 res 列表中。另外，将 K 减少 1。
步骤 4 - 遍历"res"列表并打印其值。
示例
#include <bits/stdc++.h>
using namespace std;
void printMinDistance(int nums[], int K, int n) {
// 映射以存储访问过的点
map<int, int> num_map;
queue<int> que;
// 在映射和队列中插入数组元素
for (int p = 0; p < n; ++p) {
num_map[nums[p]] = 1;
que.push(nums[p]);
}
vector<int> res;
// BFS 算法
while (K > 0) {
// 从队列中弹出第一个元素
int temp = que.front();
que.pop();
// 如果尚未访问 temp - 1
if (!num_map[temp - 1] && K > 0) {
num_map[temp - 1] = 1;
que.push(temp - 1);
res.push_back(temp - 1);
K--;
}
// 如果 temp + 1 未被访问
if (!num_map[temp + 1] && K > 0) {
num_map[temp + 1] = 1;
que.push(temp + 1);
res.push_back(temp + 1);
K--;
}
}
cout << "K 个点为：";
for (auto p : res)
cout << p << " ";
}
int main() {
int nums[] = {2, 3, 5, 7, -10, 12};
int K = 5;
int n = sizeof(nums) / sizeof(nums[0]);
printMinDistance(nums, K, n);
return 0;
}
输出
K 个点为：1 4 6 8 -11
时间复杂度 − O(N + K)，其中 N 是数组的大小，K 是我们需要查找的元素数量。
空间复杂度 − O(N + K)，将元素存储到映射中。
结论
我们找到了数组元素的 K 个最近元素。当元素在 {x, y} 对中给出时，程序员可能会尝试找到 K 个最近元素，为此，您需要使用欧几里得距离。
