使用廣度優先搜尋 (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個最接近的元素，為此，需要使用歐幾里得距離。