C++ 使用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 - 定义’map’和’queue’。还定义’res’列表来存储K个最近的元素。
步骤2 - 遍历数组元素并将元素插入map和queue中。
步骤3 - 使用while循环进行K次迭代。
步骤3.1 - 从队列中弹出第一个元素，并将其存储在’temp’变量中。
步骤3.2 - 如果temp-1未被访问且K大于0，则将temp-1插入map和queue中。同时将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 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;
}