使用广度优先搜索 (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等等。

方法

在这种方法中，我们将使用map来跟踪原始数组元素和其他最接近的元素。我们还将继续将最接近的元素插入队列。之后，如果需要更多元素，我们可以取先前最接近元素的最接近元素以最小化距离。

算法

• 步骤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插入映射、队列和res列表。同时，将K减1。

• 步骤4 − 遍历'res'列表并打印其值。

示例

#include <bits/stdc++.h>
using namespace std;

void printMinDistance(int nums[], int K, int n) {
   // Map to store visited points
   map<int, int> num_map;
   queue<int> que;
   // Insert array elements in the map and queue
   for (int p = 0; p < n; ++p) {
      num_map[nums[p]] = 1;
      que.push(nums[p]);
   }
   vector<int> res;
   // BFS algorithm
   while (K > 0) {
      // Pop the first element from the queue
      int temp = que.front();
      que.pop();
      // If temp - 1 is not visited yet
      if (!num_map[temp - 1] && K > 0) {
         num_map[temp - 1] = 1;
         que.push(temp - 1);
         res.push_back(temp - 1);
         K--;
      }
      // If temp + 1 is not visited
      if (!num_map[temp + 1] && K > 0) {
         num_map[temp + 1] = 1;
         que.push(temp + 1);
         res.push_back(temp + 1);
         K--;
      }
   }
   cout << "The K points are: ";
   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;
}

输出

The K points are: 1 4 6 8 -11

• 时间复杂度 − O(N + K)，其中N是数组的大小，K是我们需要找到的元素的数量。

• 空间复杂度 − O(N + K)，用于将元素存储到映射中。

结论

我们找到了数组元素的K个最接近的元素。程序员可以尝试在元素以{x, y}对的形式给出时查找K个最接近的元素，为此，需要使用欧几里得距离。