Dada una array de N enteros y un entero K, elija dos elementos distintos cuya suma sea K y encuentre la distancia máxima más corta de los elementos seleccionados desde los puntos finales.
Ejemplos:
Input : a[] = {2, 4, 3, 2, 1}
k = 5.
Output : 2
Explanation:
Select the pair(4, 1).
Shortest distance of 4 from ends = 2
Shortest distance of 1 from ends = 1
Hence, answer is max(2, 1) = 2
Input : a[] = {2, 4, 1, 9, 5}
k = 3
Output : 3
Explanation:
Select the pair (2, 1)
Shortest distance of 2 from ends = 1
Shortest distance of 1 from ends = 3
Hence, answer is max(1, 3) = 3.
Nota: La distancia de los elementos finales desde los extremos es 1 y no 0.
Enfoque ingenuo: el enfoque es ejecutar dos bucles y en el bucle interno verificar si dos elementos están formando un par con la suma k. En caso afirmativo, entonces haga la respuesta como el máximo de las distancias más cortas de dos elementos, compárela con la respuesta del par anterior y haga la respuesta como el mínimo de estos dos. Cuando finaliza el bucle, obtenemos la salida deseada.
Enfoque eficiente: claramente, la distancia más corta es la distancia desde el extremo izquierdo y la distancia desde el extremo derecho, es decir, 
. Denotemos la distancia más corta del i-ésimo elemento como 
. Hay otro caso en el que se repite un elemento del par seleccionado y luego se selecciona el mínimo de todas las distancias más cortas de aparición de ese elemento. Ejecute un ciclo y almacene la distancia más corta de todos los elementos de la array en otra array (déjelo ser ![D[]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-dfd2ca95650c392521f9b4292c6741d1_l3.png "Rendered by QuickLaTeX.com")
). Ahora, tenemos las distancias más cortas de todos los elementos.
Ejecute un bucle for. Si el elemento elegido es x , entonces el otro elemento debería ser kx . Actualice las respuestas con ![max(D[x], D[k-x])](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-b63514b47898d1c2af3c1675456f51cb_l3.png "Rendered by QuickLaTeX.com")
y en cada actualización, seleccione el mínimo de respuesta anterior y actual. Si kx no está en la array, entonces ![D[k-x]](https://www.geeksforgeeks.org/wp-content/ql-cache/quicklatex.com-254b61146048ad4393a0be8d224b49a2_l3.png "Rendered by QuickLaTeX.com")
será INFINITO, que ya se inicializará.
Implementación:
C++
// C++ code to find maximum shortest distance
// from endpoints
#include <bits/stdc++.h>
using namespace std;
// function to find maximum shortest distance
int find_maximum(int a[], int n, int k)
{
// stores the shortest distance of every
// element in original array.
unordered_map<int, int> b;
for (int i = 0; i < n; i++) {
int x = a[i];
// shortest distance from ends
int d = min(1 + i, n - i);
if (b.find(x) == b.end())
b[x] = d;
else
/* if duplicates are found, b[x]
is replaced with minimum of the
previous and current position's
shortest distance*/
b[x] = min(d, b[x]);
}
int ans = INT_MAX;
for (int i = 0; i < n; i++) {
int x = a[i];
// similar elements ignore them
// cause we need distinct elements
if (x != k - x && b.find(k - x) != b.end())
ans = min(max(b[x], b[k - x]), ans);
}
return ans;
}
// driver code
int main()
{
int a[] = { 3, 5, 8, 6, 7 };
int K = 11;
int n = sizeof(a) / sizeof(a[0]);
cout << find_maximum(a, n, K) << endl;
return 0;
}
Java
// Java code to find maximum shortest distance
// from endpoints
import java.util.*;
class GFG
{
static void makePermutation(int []a, int n)
{
// Store counts of all elements.
HashMap<Integer,
Integer> count = new HashMap<Integer,
Integer>();
for (int i = 0; i < n; i++)
{
if(count.containsKey(a[i]))
{
count.put(a[i], count.get(a[i]) + 1);
}
else
{
count.put(a[i], 1);
}
}
}
// function to find maximum shortest distance
static int find_maximum(int a[], int n, int k)
{
// stores the shortest distance of every
// element in original array.
HashMap<Integer,
Integer> b = new HashMap<Integer,
Integer>();
for (int i = 0; i < n; i++)
{
int x = a[i];
// shortest distance from ends
int d = Math.min(1 + i, n - i);
if (!b.containsKey(x))
b.put(x, d);
else
{
/* if duplicates are found, b[x]
is replaced with minimum of the
previous and current position's
shortest distance*/
b. put(x, Math.min(d, b.get(x)));
}
}
int ans = Integer.MAX_VALUE;
for (int i = 0; i < n; i++)
{
int x = a[i];
// similar elements ignore them
// cause we need distinct elements
if (x != k - x && b.containsKey(k - x))
ans = Math.min(Math.max(b.get(x),
b.get(k - x)), ans);
}
return ans;
}
// Driver Code
public static void main(String[] args)
{
int a[] = { 3, 5, 8, 6, 7 };
int K = 11;
int n = a.length;
System.out.println(find_maximum(a, n, K));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 code to find maximum shortest # distance from endpoints # function to find maximum shortest distance def find_maximum(a, n, k): # stores the shortest distance of every # element in original array. b = dict() for i in range(n): x = a[i] # shortest distance from ends d = min(1 + i, n - i) if x not in b.keys(): b[x] = d else: # if duplicates are found, b[x] # is replaced with minimum of the # previous and current position's # shortest distance*/ b[x] = min(d, b[x]) ans = 10**9 for i in range(n): x = a[i] # similar elements ignore them # cause we need distinct elements if (x != (k - x) and (k - x) in b.keys()): ans = min(max(b[x], b[k - x]), ans) return ans # Driver code a = [3, 5, 8, 6, 7] K = 11 n = len(a) print(find_maximum(a, n, K)) # This code is contributed by mohit kumar
C#
// C# code to find maximum shortest distance
// from endpoints
using System;
using System.Collections.Generic;
class GFG
{
static void makePermutation(int []a, int n)
{
// Store counts of all elements.
Dictionary<int,
int> count = new Dictionary<int,
int>();
for (int i = 0; i < n; i++)
{
if(count.ContainsKey(a[i]))
{
count[a[i]] = count[a[i]] + 1;
}
else
{
count.Add(a[i], 1);
}
}
}
// function to find maximum shortest distance
static int find_maximum(int []a, int n, int k)
{
// stores the shortest distance of every
// element in original array.
Dictionary<int,
int> b = new Dictionary<int,
int>();
for (int i = 0; i < n; i++)
{
int x = a[i];
// shortest distance from ends
int d = Math.Min(1 + i, n - i);
if (!b.ContainsKey(x))
b.Add(x, d);
else
{
/* if duplicates are found, b[x]
is replaced with minimum of the
previous and current position's
shortest distance*/
b[x] = Math.Min(d, b[x]);
}
}
int ans = int.MaxValue;
for (int i = 0; i < n; i++)
{
int x = a[i];
// similar elements ignore them
// cause we need distinct elements
if (x != k - x && b.ContainsKey(k - x))
ans = Math.Min(Math.Max(b[x],
b[k - x]), ans);
}
return ans;
}
// Driver Code
public static void Main(String[] args)
{
int []a = { 3, 5, 8, 6, 7 };
int K = 11;
int n = a.Length;
Console.WriteLine(find_maximum(a, n, K));
}
}
// This code is contributed by Princi Singh
Javascript
<script>
// JavaScript code to find maximum shortest distance
// from endpoints
function makePermutation(a,n)
{
// Store counts of all elements.
let count = new Map();
for (let i = 0; i < n; i++)
{
if(count.has(a[i]))
{
count.set(a[i], count.get(a[i]) + 1);
}
else
{
count.set(a[i], 1);
}
}
}
// function to find maximum shortest distance
function find_maximum(a,n,k)
{
// stores the shortest distance of every
// element in original array.
let b = new Map();
for (let i = 0; i < n; i++)
{
let x = a[i];
// shortest distance from ends
let d = Math.min(1 + i, n - i);
if (!b.has(x))
b.set(x, d);
else
{
/* if duplicates are found, b[x]
is replaced with minimum of the
previous and current position's
shortest distance*/
b. set(x, Math.min(d, b.get(x)));
}
}
let ans = Number.MAX_VALUE;
for (let i = 0; i < n; i++)
{
let x = a[i];
// similar elements ignore them
// cause we need distinct elements
if (x != k - x && b.has(k - x))
ans = Math.min(Math.max(b.get(x),
b.get(k - x)), ans);
}
return ans;
}
// Driver Code
let a=[3, 5, 8, 6, 7 ];
let K = 11;
let n = a.length;
document.write(find_maximum(a, n, K));
// This code is contributed by patel2127
</script>
Producción:
2
Tiempo Complejidad : O(n)
Espacio Auxiliar : O(n)
Publicación traducida automáticamente
Artículo escrito por Harsha_Mogali y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA