Dada una array que representa n posiciones a lo largo de una línea recta. Encuentre k (donde k <= n) elementos de la array de modo que se maximice la distancia mínima entre dos (puntos consecutivos entre los k puntos).
Ejemplos:
Input : arr[] = {1, 2, 8, 4, 9}
k = 3
Output : 3
Largest minimum distance = 3
3 elements arranged at positions 1, 4 and 8,
Resulting in a minimum distance of 3
Input : arr[] = {1, 2, 7, 5, 11, 12}
k = 3
Output : 5
Largest minimum distance = 5
3 elements arranged at positions 1, 7 and 12,
resulting in a minimum distance of 5 (between
7 and 12)
Una solución ingenua es considerar todos los subconjuntos de tamaño 3 y encontrar la distancia mínima para cada subconjunto. Finalmente, devuelva la mayor de todas las distancias mínimas.
Una solución eficiente se basa en la búsqueda binaria . Primero ordenamos la array. Ahora sabemos que el resultado del valor máximo posible es arr[n-1] – arr[0] (para k = 2). Hacemos una búsqueda binaria del resultado máximo para k dado. Comenzamos con la mitad del máximo resultado posible. Si el medio es una solución factible, buscamos en la mitad derecha del medio. De lo contrario, la búsqueda se deja a la mitad. Para comprobar la viabilidad, colocamos k elementos bajo la distancia media dada.
Implementación:
C++
// C++ program to find largest minimum distance
// among k points.
#include <bits/stdc++.h>
using namespace std;
// Returns true if it is possible to arrange
// k elements of arr[0..n-1] with minimum distance
// given as mid.
bool isFeasible(int mid, int arr[], int n, int k)
{
// Place first element at arr[0] position
int pos = arr[0];
// Initialize count of elements placed.
int elements = 1;
// Try placing k elements with minimum
// distance mid.
for (int i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
// Place next element if its
// distance from the previously
// placed element is greater
// than current mid
pos = arr[i];
elements++;
// Return if all elements are placed
// successfully
if (elements == k)
return true;
}
}
return 0;
}
// Returns largest minimum distance for k elements
// in arr[0..n-1]. If elements can't be placed,
// returns -1.
int largestMinDist(int arr[], int n, int k)
{
// Sort the positions
sort(arr, arr + n);
// Initialize result.
int res = -1;
// Consider the maximum possible distance
//here we are using right value as highest distance difference,
//so we remove some extra checks
int left = 1, right = arr[n - 1];
// left is initialized with 1 and not with arr[0]
// because, minimum distance between each element
// can be one and not arr[0]. consider this example:
// arr[] = {9,12} and you have to place 2 element
// then left = arr[0] will force the function to
// look the answer between range arr[0] to arr[n-1],
// i.e 9 to 12, but the answer is 3 so It is required
// that you initialize the left with 1
// Do binary search for largest minimum distance
while (left < right) {
int mid = (left + right) / 2;
// If it is possible to place k elements
// with minimum distance mid, search for
// higher distance.
if (isFeasible(mid, arr, n, k)) {
// Change value of variable max to mid if
// all elements can be successfully placed
res = max(res, mid);
left = mid + 1;
}
// If not possible to place k elements, search
// for lower distance
else
right = mid;
}
return res;
}
// Driver code
int main()
{
int arr[] = { 1, 2, 8, 4, 9 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
cout << largestMinDist(arr, n, k);
return 0;
}
Java
// Java program to find largest
// minimum distance among k points.
import java.util.Arrays;
class GFG {
// Returns true if it is possible to
// arrange k elements of arr[0..n-1]
// with minimum distance given as mid.
static boolean isFeasible(int mid, int arr[], int n,
int k)
{
// Place first element at arr[0] position
int pos = arr[0];
// Initialize count of elements placed.
int elements = 1;
// Try placing k elements with minimum
// distance mid.
for (int i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
// Place next element if its
// distance from the previously
// placed element is greater
// than current mid
pos = arr[i];
elements++;
// Return if all elements are
// placed successfully
if (elements == k)
return true;
}
}
return false;
}
// Returns largest minimum distance for
// k elements in arr[0..n-1]. If elements
// can't be placed, returns -1.
static int largestMinDist(int arr[], int n, int k)
{
// Sort the positions
Arrays.sort(arr);
// Initialize result.
int res = -1;
// Consider the maximum possible distance
int left = 1, right = arr[n - 1];
// left is initialized with 1 and not with arr[0]
// because, minimum distance between each element
// can be one and not arr[0]. consider this example:
// arr[] = {9,12} and you have to place 2 element
// then left = arr[0] will force the function to
// look the answer between range arr[0] to arr[n-1],
// i.e 9 to 12, but the answer is 3 so It is
// required that you initialize the left with 1
// Do binary search for largest
// minimum distance
while (left < right) {
int mid = (left + right) / 2;
// If it is possible to place k
// elements with minimum distance mid,
// search for higher distance.
if (isFeasible(mid, arr, n, k)) {
// Change value of variable max to
// mid if all elements can be
// successfully placed
res = Math.max(res, mid);
left = mid + 1;
}
// If not possible to place k elements,
// search for lower distance
else
right = mid;
}
return res;
}
// driver code
public static void main(String[] args)
{
int arr[] = { 1, 2, 8, 4, 9 };
int n = arr.length;
int k = 3;
System.out.print(largestMinDist(arr, n, k));
}
}
// This code is contributed by Anant Agarwal.
Python3
# Python 3 program to find largest minimum
# distance among k points.
# Returns true if it is possible to arrange
# k elements of arr[0..n-1] with minimum
# distance given as mid.
def isFeasible(mid, arr, n, k):
# Place first element at arr[0] position
pos = arr[0]
# Initialize count of elements placed.
elements = 1
# Try placing k elements with minimum
# distance mid.
for i in range(1, n, 1):
if (arr[i] - pos >= mid):
# Place next element if its distance
# from the previously placed element
# is greater than current mid
pos = arr[i]
elements += 1
# Return if all elements are placed
# successfully
if (elements == k):
return True
return 0
# Returns largest minimum distance for k elements
# in arr[0..n-1]. If elements can't be placed,
# returns -1.
def largestMinDist(arr, n, k):
# Sort the positions
arr.sort(reverse=False)
# Initialize result.
res = -1
# Consider the maximum possible distance
left = 1
right = arr[n - 1]
# left is initialized with 1 and not with arr[0]
# because, minimum distance between each element
# can be one and not arr[0]. consider this example:
# arr[] = {9,12} and you have to place 2 element
# then left = arr[0] will force the function to
# look the answer between range arr[0] to arr[n-1],
# i.e 9 to 12, but the answer is 3 so It is required
# that you initialize the left with 1
# Do binary search for largest
# minimum distance
while (left < right):
mid = (left + right) / 2
# If it is possible to place k elements
# with minimum distance mid, search for
# higher distance.
if (isFeasible(mid, arr, n, k)):
# Change value of variable max to mid if
# all elements can be successfully placed
res = max(res, mid)
left = mid + 1
# If not possible to place k elements,
# search for lower distance
else:
right = mid
return res
# Driver code
if __name__ == '__main__':
arr = [1, 2, 8, 4, 9]
n = len(arr)
k = 3
print(largestMinDist(arr, n, k))
# This code is contributed by
# Sanjit_prasad
C#
// C# program to find largest
// minimum distance among k points.
using System;
public class GFG {
// Returns true if it is possible to
// arrange k elements of arr[0..n-1]
// with minimum distance given as mid.
static bool isFeasible(int mid, int[] arr, int n, int k)
{
// Place first element at arr[0]
// position
int pos = arr[0];
// Initialize count of elements placed.
int elements = 1;
// Try placing k elements with minimum
// distance mid.
for (int i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
// Place next element if its
// distance from the previously
// placed element is greater
// than current mid
pos = arr[i];
elements++;
// Return if all elements are
// placed successfully
if (elements == k)
return true;
}
}
return false;
}
// Returns largest minimum distance for
// k elements in arr[0..n-1]. If elements
// can't be placed, returns -1.
static int largestMinDist(int[] arr, int n, int k)
{
// Sort the positions
Array.Sort(arr);
// Initialize result.
int res = -1;
// Consider the maximum possible
// distance
int left = 1, right = arr[n - 1];
// left is initialized with 1 and not with arr[0]
// because, minimum distance between each element
// can be one and not arr[0]. consider this example:
// arr[] = {9,12} and you have to place 2 element
// then left = arr[0] will force the function to
// look the answer between range arr[0] to arr[n-1],
// i.e 9 to 12, but the answer is 3 so It is
// required that you initialize the left with 1
// Do binary search for largest
// minimum distance
while (left < right) {
int mid = (left + right) / 2;
// If it is possible to place k
// elements with minimum distance
// mid, search for higher distance.
if (isFeasible(mid, arr, n, k)) {
// Change value of variable
// max to mid if all elements
// can be successfully placed
res = Math.Max(res, mid);
left = mid + 1;
}
// If not possible to place k
// elements, search for lower
// distance
else
right = mid;
}
return res;
}
// driver code
public static void Main()
{
int[] arr = { 1, 2, 8, 4, 9 };
int n = arr.Length;
int k = 3;
Console.WriteLine(largestMinDist(arr, n, k));
}
}
// This code is contributed by Sam007.
PHP
<?php
// PHP program to find largest
// minimum distance among k points.
// Returns true if it is possible
// to arrange k elements of
// arr[0..n-1] with minimum
// distance given as mid.
function isFeasible($mid, $arr,
$n, $k)
{
// Place first element
// at arr[0] position
$pos = $arr[0];
// Initialize count of
// elements placed.
$elements = 1;
// Try placing k elements
// with minimum distance mid.
for ($i = 1; $i < $n; $i++)
{
if ($arr[$i] - $pos >= $mid)
{
// Place next element if
// its distance from the
// previously placed
// element is greater
// than current mid
$pos = $arr[$i];
$elements++;
// Return if all elements
// are placed successfully
if ($elements == $k)
return true;
}
}
return 0;
}
// Returns largest minimum
// distance for k elements
// in arr[0..n-1]. If elements
// can't be placed, returns -1.
function largestMinDist($arr, $n, $k)
{
// Sort the positions
sort($arr);
// Initialize result.
$res = -1;
// Consider the maximum
// possible distance
$left = 1;
$right = $arr[$n - 1];
// left is initialized with 1 and not with arr[0]
// because, minimum distance between each element
// can be one and not arr[0]. consider this example:
// arr[] = {9,12} and you have to place 2 element
// then left = arr[0] will force the function to
// look the answer between range arr[0] to arr[n-1],
// i.e 9 to 12, but the answer is 3 so It is required
// that you initialize the left with 1
// Do binary search for
// largest minimum distance
while ($left < $right)
{
$mid = ($left + $right) / 2;
// If it is possible to place
// k elements with minimum
// distance mid, search for
// higher distance.
if (isFeasible($mid, $arr,
$n, $k))
{
// Change value of variable
// max to mid if all elements
// can be successfully placed
$res = max($res, $mid);
$left = $mid + 1;
}
// If not possible to place
// k elements, search for
// lower distance
else
$right = $mid;
}
return $res;
}
// Driver Code
$arr = array(1, 2, 8, 4, 9);
$n = sizeof($arr);
$k = 3;
echo largestMinDist($arr, $n, $k);
// This code is contributed by aj_36
?>
Javascript
<script>
// Javascript program to find largest
// minimum distance among k points.
// Returns true if it is possible to
// arrange k elements of arr[0..n-1]
// with minimum distance given as mid.
function isFeasible(mid, arr, n, k)
{
// Place first element at arr[0]
// position
let pos = arr[0];
// Initialize count of elements placed.
let elements = 1;
// Try placing k elements with minimum
// distance mid.
for (let i = 1; i < n; i++) {
if (arr[i] - pos >= mid) {
// Place next element if its
// distance from the previously
// placed element is greater
// than current mid
pos = arr[i];
elements++;
// Return if all elements are
// placed successfully
if (elements == k)
return true;
}
}
return false;
}
// Returns largest minimum distance for
// k elements in arr[0..n-1]. If elements
// can't be placed, returns -1.
function largestMinDist(arr, n, k)
{
// Sort the positions
arr.sort(function(a, b){return a - b});
// Initialize result.
let res = -1;
// Consider the maximum possible
// distance
let left = 1, right = arr[n - 1];
// left is initialized with 1 and not with arr[0]
// because, minimum distance between each element
// can be one and not arr[0]. consider this example:
// arr[] = {9,12} and you have to place 2 element
// then left = arr[0] will force the function to
// look the answer between range arr[0] to arr[n-1],
// i.e 9 to 12, but the answer is 3 so It is
// required that you initialize the left with 1
// Do binary search for largest
// minimum distance
while (left < right) {
let mid = parseInt((left + right) / 2, 10);
// If it is possible to place k
// elements with minimum distance
// mid, search for higher distance.
if (isFeasible(mid, arr, n, k)) {
// Change value of variable
// max to mid if all elements
// can be successfully placed
res = Math.max(res, mid);
left = mid + 1;
}
// If not possible to place k
// elements, search for lower
// distance
else
right = mid;
}
return res;
}
let arr = [ 1, 2, 8, 4, 9 ];
let n = arr.length;
let k = 3;
document.write(largestMinDist(arr, n, k));
</script>
Producción
3
Complejidad de tiempo: O (nlog n), donde n es la longitud de la array.
Competencia espacial : O(1)
Este artículo es una contribución de Raghav Jajodia . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA