# 用BFS求出与给定整数集距离最小的积分点

2021年4月29日18:29:09 发表评论 866 次浏览

## 本文概述

A[]中-2的最近点是-1 -> distance = 1
A[]中0的最近点是-1 -> distance = 1
A[]中3的最近点是4 -> distance = 1

A []中-1的最近点是0-> distance = 1
A []中2的最近点是3->distance= 1
A []中5的最近点是4->距离= 1
A []中-2的最近点是0->距离= 2
6的最近点在A []中为4->距离= 2

1. 我们首先将给定的整数集作为根元素并将其压入队列和杂凑.
2. 然后对于任何说X的元素, 我们将仅使用哈希图检查是否遇到(X-1)或(X + 1)。如果到目前为止还没有遇到任何问题, 那么我们将该元素推送到答案数组中, 并同时进行队列和哈希处理。
3. 重复此过程, 直到遇到K个新元素。

## C ++

``````//C++ implementation of above approach

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

//Function to find points at
//minimum distance
void minDistancePoints( int A[], int K, int n)
{

//Hash to store points
//that are encountered
map<int , int> m;

//Queue to store initial
//set of points
queue<int> q;

for ( int i = 0; i <n; ++i) {
m[A[i]] = 1;
q.push(A[i]);
}

//Vector to store integral
//points
vector<int> ans;

//Using bfs to visit nearest
//visited points
while (K> 0) {

//Get first element from
//queue
int x = q.front();
q.pop();

//Check if (x-1) is not
//encountered so far
if (!m[x - 1] && K> 0) {
//Update hash with
//this new element
m[x - 1] = 1;

//Insert (x-1) into
//queue
q.push(x - 1);

//Push (x-1) as
//new element
ans.push_back(x - 1);

//Decrement counter
//by 1
K--;
}

//Check if (x+1) is not
//encountered so far
if (!m[x + 1] && K> 0) {
//Update hash with
//this new element
m[x + 1] = 1;

//Insert (x+1) into
//queue
q.push(x + 1);

//Push (x+1) as
//new element
ans.push_back(x + 1);

//Decrement counter
//by 1
K--;
}
}

//Print result array
for ( auto i : ans)
cout <<i <<" " ;
}

//Driver code
int main()
{

int A[] = { -1, 4, 6 };
int K = 3;
int n = sizeof (A) /sizeof (A[0]);

minDistancePoints(A, K, n);

return 0;
}``````

## Java

``````//Java implementation of above approach
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

class Geeks{

//Function to find points at
//minimum distance
static void minDistancePoints( int A[], int K, int n)
{

//Hash to store points
//that are encountered
Map<Integer, Boolean> m = new HashMap<Integer, Boolean>();

//Queue to store initial
//set of points

for ( int i = 0 ; i <n; ++i)
{
m.put(A[i], true );
}

//List to store integral
//points

//Using bfs to visit nearest
//visited points
while (K> 0 )
{

//Get first element from
//queue
int x = q.poll();

//Check if (x-1) is not
//encountered so far
if (!m.containsKey(x - 1 ) && K> 0 )
{

//Update hash with
//this new element
m.put(x - 1 , true );

//Insert (x-1) into
//queue

//Push (x-1) as
//new element

//Decrement counter
//by 1
K--;
}

//Check if (x+1) is not
//encountered so far
if (!m.containsKey(x + 1 ) && K> 0 )
{

//Update hash with
//this new element
m.put(x + 1 , true );

//Insert (x+1) into
//queue

//Push (x+1) as
//new element

//Decrement counter
//by 1
K--;
}
}

//Print result array
for (Integer i : ans)
System.out.print(i + " " );
}

//Driver code
public static void main(String[] args)
{
int A[] = new int [] { - 1 , 4 , 6 };
int K = 3 ;
int n = A.length;

minDistancePoints(A, K, n);
}
}

//This code is contributed by Rajnis09``````

## Python3

``````# Python 3 implementation
# of above approach

# Function to find points
# at minimum distance
def minDistancePoints(A, K, n):

# Hash to store points
# that are encountered
m = {}

# Queue to store initial
# set of points
q = []

for i in range (n):
m[A[i]] = 1
q.append(A[i])

# Vector to store
# integral points
ans = []

# Using bfs to visit nearest
# visited points
while (K> 0 ):

# Get first element from
# queue
x = q[ 0 ]
q = q[ 1 ::]

# Check if (x-1) is not
# encountered so far
if ((x - 1 ) not in m and
K> 0 ):

# Update hash with
# this new element
m[x - 1 ] = m.get(x - 1 , 0 ) + 1

# Insert (x-1) into
# queue
q.append(x - 1 )

# Push (x-1) as
# new element
ans.append(x - 1 )

# Decrement counter
# by 1
K - = 1

# Check if (x+1) is not
# encountered so far
if ((x + 1 ) not in m and
K> 0 ):
# Update hash with
# this new element
m[x + 1 ] = m.get(x + 1 , 0 ) + 1

# Insert (x+1) into
# queue
q.append(x + 1 )

# Push (x+1) as
# new element
ans.append(x + 1 )
# Decrement counter
# by 1
K - = 1

# Print result array
for i in ans:
print (i, end = " " )

# Driver code
if __name__ = = '__main__' :

A =  [ - 1 , 4 , 6 ]
K = 3
n =  len (A)
minDistancePoints(A, K, n)

# This code is contributed by bgangwar59``````

## C#

``````//C# implementation of above approach
using System;
using System.Collections.Generic;

class GFG{

//Function to find points at
//minimum distance
static void minDistancePoints( int []A, int K, int n)
{

//Hash to store points
//that are encountered
Dictionary<int , Boolean> m = new Dictionary<int , Boolean>();

//Queue to store initial
//set of points
Queue<int> q = new Queue<int>();

for ( int i = 0; i <n; ++i)
{
q.Enqueue(A[i]);
}

//List to store integral
//points
List<int> ans = new List<int>();

//Using bfs to visit nearest
//visited points
while (K> 0)
{

//Get first element from
//queue
int x = q.Dequeue();

//Check if (x-1) is not
//encountered so far
if (!m.ContainsKey(x - 1) && K> 0)
{

//Update hash with
//this new element

//Insert (x-1) into
//queue
q.Enqueue(x - 1);

//Push (x-1) as
//new element

//Decrement counter
//by 1
K--;
}

//Check if (x+1) is not
//encountered so far
if (!m.ContainsKey(x + 1) && K> 0)
{

//Update hash with
//this new element

//Insert (x+1) into
//queue
q.Enqueue(x + 1);

//Push (x+1) as
//new element

//Decrement counter
//by 1
K--;
}
}

//Print result array
foreach ( int i in ans)
Console.Write(i + " " );
}

//Driver code
public static void Main(String[] args)
{
int []A = new int [] { -1, 4, 6 };
int K = 3;
int n = A.Length;

minDistancePoints(A, K, n);
}
}

//This code is contributed by Amit Katiyar``````

``-2 0 3``