Dada una array de enteros A[] de longitud N y un entero K . La tarea es encontrar K puntos integrales distintos que no están presentes en la array dada, de modo que la suma de sus distancias desde el punto más cercano en A[] se minimice.
Un punto integral se define como el punto con ambas coordenadas como números enteros. Además, en el eje x, no necesitamos considerar la coordenada y porque la coordenada y de todos los puntos es igual a cero.
Ejemplos:
Entrada: A[] = { -1, 4, 6 }, K = 3
Salida: -2, 0, 3
Explicación:
El punto más cercano para -2 en A[] es -1 -> distancia = 1
Punto más cercano para 0 en A[] es -1 -> distancia = 1
El punto más cercano para 3 en A[] es 4 -> distancia = 1
Distancia total = 1 + 1 + 1 = 3 que es la distancia mínima posible.
También son posibles otros resultados con la misma distancia mínima.
Entrada: A[] = { 0, 1, 3, 4 }, K = 5
Salida: -1, 2, 5, -2, 6
Explicación:
El punto más cercano para -1 en A[] es 0 -> distancia = 1
El punto más cercano para 2 en A[] es 3 -> distancia = 1
El punto más cercano para 5 en A[] es 4 -> distancia = 1
El punto más cercano para -2 en A[] es 0 -> distancia = 2
El punto más cercano para 6 en A[] es 4 -> distancia = 2
Distancia total = 2 + 1 + 1 + 1 + 2 = 7 que es la distancia mínima posible.
Enfoque: Resolveremos este problema usando el concepto de búsqueda primero en anchura .
- Inicialmente asumiremos el conjunto dado de enteros como el elemento raíz y lo insertaremos en Queue and Hash .
- Luego, para cualquier elemento, digamos X, simplemente verificaremos si (X-1) o (X + 1) se encuentra o no usando un hashmap. Si alguno de ellos no se encuentra hasta el momento, empujamos ese elemento en nuestra array de respuesta y cola y hash también.
- Repita esto hasta que encontremos K nuevos elementos.
A continuación se muestra la implementación del enfoque anterior.
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
// points from already
// 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.LinkedList;
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
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0; i < n; ++i)
{
m.put(A[i], true);
q.add(A[i]);
}
// List to store integral
// points
LinkedList<Integer> ans = new LinkedList<Integer>();
// Using bfs to visit nearest
// points from already
// 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
q.add(x - 1);
// Push (x-1) as
// new element
ans.add(x - 1);
// 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
q.add(x + 1);
// Push (x+1) as
// new element
ans.add(x + 1);
// 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
# points from already
# 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)
{
m.Add(A[i], true);
q.Enqueue(A[i]);
}
// List to store integral
// points
List<int> ans = new List<int>();
// Using bfs to visit nearest
// points from already
// 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
m.Add(x - 1, true);
// Insert (x-1) into
// queue
q.Enqueue(x - 1);
// Push (x-1) as
// new element
ans.Add(x - 1);
// 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.Add(x + 1, true);
// Insert (x+1) into
// queue
q.Enqueue(x + 1);
// Push (x+1) as
// new element
ans.Add(x + 1);
// 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
Javascript
<script>
// Javascript implementation of above approach
// Function to find points at
// minimum distance
function minDistancePoints(A, K, n)
{
// Hash to store points
// that are encountered
let m = new Map();
// Queue to store initial
// set of points
let q = [];
for(let i = 0; i < n; ++i)
{
m.set(A[i], true);
q.push(A[i]);
}
// List to store integral
// points
let ans = [];
// Using bfs to visit nearest
// points from already
// visited points
while (K > 0)
{
// Get first element from
// queue
let x = q.shift();
// Check if (x-1) is not
// encountered so far
if (!m.has(x - 1) && K > 0)
{
// Update hash with
// this new element
m.set(x - 1, true);
// Insert (x-1) into
// queue
q.push(x - 1);
// Push (x-1) as
// new element
ans.push(x - 1);
// Decrement counter
// by 1
K--;
}
// Check if (x+1) is not
// encountered so far
if (!m.has(x + 1) && K > 0)
{
// Update hash with
// this new element
m.set(x + 1, true);
// Insert (x+1) into
// queue
q.push(x + 1);
// Push (x+1) as
// new element
ans.push(x + 1);
// Decrement counter
// by 1
K--;
}
}
// Print result array
for(let i = 0; i < ans.length; i++)
document.write(ans[i] + " ");
}
let A = [ -1, 4, 6 ];
let K = 3;
let n = A.length;
minDistancePoints(A, K, n);
// This code is contributed by divyeshrabadiya07.
</script>
Producción:
-2 0 3
Complejidad de tiempo: O(M*log(M)) , donde M = N + K.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA