Dada una array de N enteros, la tarea es seleccionar K elementos de estos N elementos de tal manera que la diferencia mínima entre cada uno de los K números sea la Mayor. Devuelve la diferencia mínima más grande después de elegir cualquier elemento K.
Ejemplos:
Entrada: N = 4, K = 3, arr = [2, 6, 2, 5]
Salida: 1
Explicación: 3 elementos de 4 elementos deben seleccionarse con una diferencia mínima tan grande como sea posible. Seleccionar 2, 2, 5 dará como resultado una diferencia mínima como 0. Seleccionar 2, 5, 6 dará como resultado una diferencia mínima como 6-5=1Entrada: N = 7, K = 4, arr = [1, 4, 9, 0, 2, 13, 3]
Salida: 4
Explicación: Seleccionar 0, 4, 9, 13 dará como resultado una diferencia mínima de 4, que es la mayor diferencia mínima posible
Enfoque ingenuo: genere todos los subconjuntos de tamaño K y encuentre la diferencia mínima en todos ellos. Luego devuelva el máximo entre las diferencias.
Enfoque eficiente: el problema dado se puede resolver de manera eficiente utilizando la técnica de búsqueda binaria en la respuesta. Se pueden seguir los siguientes pasos para resolver el problema:
- Ordenar la array en orden ascendente
- Inicializar respuesta mínima ans a 1
- La búsqueda binaria se usa en el rango 1 al elemento máximo en la array arr
- La diferencia variable se usa para almacenar la diferencia mínima más grande en cada iteración
- La función de ayuda se utiliza para verificar si la selección de K elementos es posible con una diferencia mínima mayor que la diferencia calculada en la iteración anterior. Si es posible, se devuelve verdadero o, de lo contrario, se devuelve falso.
- Si la función anterior devuelve:
- Verdadero, luego actualice ans a dif y se fue a dif + 1
- Falso, luego actualice a la derecha a dif – 1
A continuación se muestra la implementación del enfoque de búsqueda binaria anterior
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// To check if selection of K elements
// is possible such that difference
// between them is greater than dif
bool isPossibleToSelect(int arr[], int N,
int dif, int K)
{
// Selecting first element in the
// sorted array
int count = 1;
// prev is the previously selected
// element initially at index 0 as
// first element is already selected
int prev = arr[0];
// Check if selection of K-1 elements
// from array with a minimum
// difference of dif is possible
for (int i = 1; i < N; i++) {
// If the current element is
// atleast dif difference apart
// from the previously selected
// element then select the current
// element and increase the count
if (arr[i] >= (prev + dif)) {
count++;
// If selection of K elements
// with a min difference of dif
// is possible then return true
if (count == K)
return true;
// Prev will become current
// element for the next iteration
prev = arr[i];
}
}
// If selection of K elements with minimum
// difference of dif is not possible
// then return false
return false;
}
int binarySearch(int arr[], int left,
int right, int K, int N)
{
// Minimum largest difference
// possible is 1
int ans = 1;
while (left <= right) {
int dif = left + (right - left) / 2;
// Check if selection of K elements
// is possible with a minimum
// difference of dif
if (isPossibleToSelect(arr, N,
dif, K)) {
// If dif is greater than
// previous ans we update ans
ans = max(ans, dif);
// Continue to search for better
// answer. Try finding greater dif
left = dif + 1;
}
// K elements cannot be selected
else
right = dif - 1;
}
return ans;
}
// Driver code
int main()
{
int N, K;
N = 7, K = 4;
int arr[] = { 1, 4, 9, 0, 2, 13, 3 };
// arr should be in a sorted order
sort(arr, arr + N);
cout << binarySearch(arr, 0, arr[N - 1], K, N)
<< "\n";
return 0;
}
Java
// Java implementation for the above approach
import java.io.*;
import java.util.Arrays;
class GFG{
// To check if selection of K elements
// is possible such that difference
// between them is greater than dif
static boolean isPossibleToSelect(int []arr, int N,
int dif, int K)
{
// Selecting first element in the
// sorted array
int count = 1;
// prev is the previously selected
// element initially at index 0 as
// first element is already selected
int prev = arr[0];
// Check if selection of K-1 elements
// from array with a minimum
// difference of dif is possible
for (int i = 1; i < N; i++) {
// If the current element is
// atleast dif difference apart
// from the previously selected
// element then select the current
// element and increase the count
if (arr[i] >= (prev + dif)) {
count++;
// If selection of K elements
// with a min difference of dif
// is possible then return true
if (count == K)
return true;
// Prev will become current
// element for the next iteration
prev = arr[i];
}
}
// If selection of K elements with minimum
// difference of dif is not possible
// then return false
return false;
}
static int binarySearch(int []arr, int left,
int right, int K, int N)
{
// Minimum largest difference
// possible is 1
int ans = 1;
while (left <= right) {
int dif = left + (right - left) / 2;
// Check if selection of K elements
// is possible with a minimum
// difference of dif
if (isPossibleToSelect(arr, N,
dif, K)) {
// If dif is greater than
// previous ans we update ans
ans = Math.max(ans, dif);
// Continue to search for better
// answer. Try finding greater dif
left = dif + 1;
}
// K elements cannot be selected
else
right = dif - 1;
}
return ans;
}
// Driver code
public static void main(String[] args)
{
int N, K;
N = 7;
K = 4;
int []arr = { 1, 4, 9, 0, 2, 13, 3 };
// arr should be in a sorted order
Arrays.sort(arr);
System.out.println(binarySearch(arr, 0, arr[N - 1], K, N));
}
}
// This code is contributed by shivanisinghss2110
Python3
# Python 3 implementation for the above approach # To check if selection of K elements # is possible such that difference # between them is greater than dif def isPossibleToSelect(arr, N, dif, K): # Selecting first element in the # sorted array count = 1 # prev is the previously selected # element initially at index 0 as # first element is already selected prev = arr[0] # Check if selection of K-1 elements # from array with a minimum # difference of dif is possible for i in range(1, N): # If the current element is # atleast dif difference apart # from the previously selected # element then select the current # element and increase the count if (arr[i] >= (prev + dif)): count += 1 # If selection of K elements # with a min difference of dif # is possible then return true if (count == K): return True # Prev will become current # element for the next iteration prev = arr[i] # If selection of K elements with minimum # difference of dif is not possible # then return false return False def binarySearch(arr, left, right, K, N): # Minimum largest difference # possible is 1 ans = 1 while (left <= right): dif = left + (right - left) // 2 # Check if selection of K elements # is possible with a minimum # difference of dif if (isPossibleToSelect(arr, N, dif, K)): # If dif is greater than # previous ans we update ans ans = max(ans, dif) # Continue to search for better # answer. Try finding greater dif left = dif + 1 # K elements cannot be selected else: right = dif - 1 return ans # Driver code if __name__ == "__main__": N = 7 K = 4 arr = [1, 4, 9, 0, 2, 13, 3] # arr should be in a sorted order arr.sort() print(binarySearch(arr, 0, arr[N - 1], K, N) ) # This code is contributed by ukasp.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
class GFG{
// To check if selection of K elements
// is possible such that difference
// between them is greater than dif
static bool isPossibleToSelect(int []arr, int N,
int dif, int K)
{
// Selecting first element in the
// sorted array
int count = 1;
// prev is the previously selected
// element initially at index 0 as
// first element is already selected
int prev = arr[0];
// Check if selection of K-1 elements
// from array with a minimum
// difference of dif is possible
for (int i = 1; i < N; i++) {
// If the current element is
// atleast dif difference apart
// from the previously selected
// element then select the current
// element and increase the count
if (arr[i] >= (prev + dif)) {
count++;
// If selection of K elements
// with a min difference of dif
// is possible then return true
if (count == K)
return true;
// Prev will become current
// element for the next iteration
prev = arr[i];
}
}
// If selection of K elements with minimum
// difference of dif is not possible
// then return false
return false;
}
static int binarySearch(int []arr, int left,
int right, int K, int N)
{
// Minimum largest difference
// possible is 1
int ans = 1;
while (left <= right) {
int dif = left + (right - left) / 2;
// Check if selection of K elements
// is possible with a minimum
// difference of dif
if (isPossibleToSelect(arr, N,
dif, K)) {
// If dif is greater than
// previous ans we update ans
ans = Math.Max(ans, dif);
// Continue to search for better
// answer. Try finding greater dif
left = dif + 1;
}
// K elements cannot be selected
else
right = dif - 1;
}
return ans;
}
// Driver code
public static void Main()
{
int N, K;
N = 7;
K = 4;
int []arr = { 1, 4, 9, 0, 2, 13, 3 };
// arr should be in a sorted order
Array.Sort(arr);
Console.Write(binarySearch(arr, 0, arr[N - 1], K, N));
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// To check if selection of K elements
// is possible such that difference
// between them is greater than dif
function isPossibleToSelect(arr, N,
dif, K)
{
// Selecting first element in the
// sorted array
let count = 1;
// prev is the previously selected
// element initially at index 0 as
// first element is already selected
let prev = arr[0];
// Check if selection of K-1 elements
// from array with a minimum
// difference of dif is possible
for (let i = 1; i < N; i++) {
// If the current element is
// atleast dif difference apart
// from the previously selected
// element then select the current
// element and increase the count
if (arr[i] >= (prev + dif)) {
count++;
// If selection of K elements
// with a min difference of dif
// is possible then return true
if (count == K)
return true;
// Prev will become current
// element for the next iteration
prev = arr[i];
}
}
// If selection of K elements with minimum
// difference of dif is not possible
// then return false
return false;
}
function binarySearch(arr, left,
right, K, N) {
// Minimum largest difference
// possible is 1
let ans = 1;
while (left <= right) {
let dif = left + Math.floor((right - left) / 2);
// Check if selection of K elements
// is possible with a minimum
// difference of dif
if (isPossibleToSelect(arr, N,
dif, K)) {
// If dif is greater than
// previous ans we update ans
ans = Math.max(ans, dif);
// Continue to search for better
// answer. Try finding greater dif
left = dif + 1;
}
// K elements cannot be selected
else
right = dif - 1;
}
return ans;
}
// Driver code
let N, K;
N = 7, K = 4;
let arr = [1, 4, 9, 0, 2, 13, 3];
// arr should be in a sorted order
arr.sort(function (a, b) { return a - b })
document.write(binarySearch(arr, 0, arr[N - 1], K, N)
+ '<br>');
// This code is contributed by Potta Lokesh
</script>
Producción
4
Complejidad temporal: O(N * log N)
Complejidad espacial: O(1)
Publicación traducida automáticamente
Artículo escrito por sinhadiptiprakash y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA