Dada una array ordenada arr[] y un entero positivo D , la tarea es encontrar el número mínimo y máximo de elementos de array que se encuentran en la distancia de D desde un elemento de array arr[i] en cualquier dirección, es decir, en el rango [arr[i] – D, arr[i]] o [arr[i], arr[i] + D] .
Ejemplos:
Entrada arr[] = {2, 4, 7, 11, 13, 14}, D = 4
Salida: 1 3
Explicación:
El número mínimo de elementos de la array que se incluye es 1 de arr[0](= 2) como allí existe solo 1 elemento que se encuentra sobre el rango [-2, 2].
El número mínimo de elementos de la array que se incluye es 3 de arr[3](= 11) ya que solo existen 3 elementos que se encuentran en el rango [11, 15].
Por lo tanto, imprime 1, 3.Entrada: arr[] = {1, 3, 5, 9, 14}, D = 5
Salida: 1 3
Enfoque: El problema dado se puede resolver usando la técnica codiciosa usando la búsqueda binaria a la izquierda y a la derecha de cada punto para verificar cuántos puntos se pueden incluir en el rango de distancia D . Siga los pasos a continuación para resolver el problema:
- Inicialice dos variables, digamos min y max para almacenar elementos mínimos y máximos incluidos en un rango de distancia D .
- Itere la array arr[] y para cada elemento realice lo siguiente:
- Inicialice una variable dist para calcular el número de puntos incluidos en un rango de distancia D .
- Realice la búsqueda binaria a la izquierda de arr[i] y encuentre elementos de array de números en el rango [arr[i] – D, arr[i]] siguiendo los siguientes pasos:
- Inicializar izquierda = 0, derecha = i – 1 y en cada iteración:
- Encuentra el valor de mid = (izquierda + derecha) / 2 .
- Si arr[mid] < arr[i] – D, entonces actualice el valor de left to mid + 1 . De lo contrario, actualice el valor de dist a mid y actualice el valor de right a mid – 1 .
- Inicializar izquierda = 0, derecha = i – 1 y en cada iteración:
- Actualice el valor de min y max según el valor de dist .
- Realice la búsqueda binaria a la izquierda de arr[i] y encuentre el número de elementos de array en el rango [arr[i], arr[i] + D] siguiendo los siguientes pasos:
- Inicialice izquierda = i + 1, derecha = N – i y en cada iteración:
- Encuentra el valor de mid = (izquierda + derecha) / 2 .
- Si arr[mid] > arr[i] + D , entonces actualice el valor de right to mid – 1 . De lo contrario, actualice el valor de dist a mid y actualice el valor de left a mid + 1 .
- Inicialice izquierda = i + 1, derecha = N – i y en cada iteración:
- Actualice el valor de min y max según el valor de dist .
- Después de completar los pasos anteriores, imprima el valor de min y max como el mínimo resultante y el número máximo de puntos cubiertos.
A continuación se muestra la implementación del enfoque anterior:
C++
// c++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to perform the Binary
// Search to the left of arr[i]
// over the given range
int leftSearch(int arr[], int val, int i)
{
// Base Case
if (i == 0)
return 1;
int left = 0, right = i - 1;
int ind = -1;
// Binary Search for index to left
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] < val) {
left = mid + 1;
}
else {
right = mid - 1;
// update index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? i - ind + 1 : 1;
}
// Function to perform the Binary
// Search to the right of arr[i]
// over the given range
int rightSearch(int arr[], int val, int i, int N)
{
// Base Case
if (i == (N - 1))
return 1;
int left = i + 1;
int right = N - 1;
int ind = -1;
// Binary Search for index to right
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > val) {
right = mid - 1;
}
else {
left = mid + 1;
// Update the index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? ind - i + 1 : 1;
}
vector<int> minMaxRange(int arr[], int D, int N)
{
// Stores the minimum and maximum
// number of points that lies
// over the distance of D
int mx = 1, mn = N;
// Iterate the array
for (int i = 0; i < N; i++) {
// Count of elements included
// to left of point at index i
int dist = leftSearch(arr, arr[i] - D, i);
// Update the minimum number
// of points
mn = min(mn, dist);
// Update the maximum number
// of points
mx = max(mx, dist);
// Count of elements included
// to right of point at index i
dist = rightSearch(arr, arr[i] + D, i, N);
// Update the minimum number
// of points
mn = min(mn, dist);
// Update the maximum number
// of points
mx = max(mx, dist);
}
// Return the array
vector<int> v;
v.push_back(mn);
v.push_back(mx);
return v;
}
// Driver Code
int main()
{
int arr[] = { 1, 3, 5, 9, 14 };
int N = 5;
int D = 4;
vector<int> minMax = minMaxRange(arr, D, N);
cout << minMax[0] << " " << minMax[1] << endl;
return 0;
}
// This code is contributed by dwivediyash
Java
// Java program for the above approach
import java.io.*;
import java.lang.Math;
import java.util.*;
class GFG {
// Function to find the minimum and
// maximum number of points included
// in a range of distance D
public static int[] minMaxRange(
int[] arr, int D, int N)
{
// Stores the minimum and maximum
// number of points that lies
// over the distance of D
int max = 1, min = N;
// Iterate the array
for (int i = 0; i < N; i++) {
// Count of elements included
// to left of point at index i
int dist = leftSearch(
arr, arr[i] - D, i);
// Update the minimum number
// of points
min = Math.min(min, dist);
// Update the maximum number
// of points
max = Math.max(max, dist);
// Count of elements included
// to right of point at index i
dist = rightSearch(
arr, arr[i] + D, i);
// Update the minimum number
// of points
min = Math.min(min, dist);
// Update the maximum number
// of points
max = Math.max(max, dist);
}
// Return the array
return new int[] { min, max };
}
// Function to perform the Binary
// Search to the left of arr[i]
// over the given range
public static int leftSearch(
int[] arr, int val, int i)
{
// Base Case
if (i == 0)
return 1;
int left = 0, right = i - 1;
int ind = -1;
// Binary Search for index to left
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] < val) {
left = mid + 1;
}
else {
right = mid - 1;
// update index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? i - ind + 1 : 1;
}
// Function to perform the Binary
// Search to the right of arr[i]
// over the given range
public static int rightSearch(
int[] arr, int val, int i)
{
// Base Case
if (i == arr.length - 1)
return 1;
int left = i + 1;
int right = arr.length - 1;
int ind = -1;
// Binary Search for index to right
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] > val) {
right = mid - 1;
}
else {
left = mid + 1;
// Update the index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? ind - i + 1 : 1;
}
// Driver Code
public static void main(String[] args)
{
int[] arr = { 1, 3, 5, 9, 14 };
int N = arr.length;
int D = 4;
int[] minMax = minMaxRange(arr, D, N);
// Function Call
System.out.print(
minMax[0] + " " + minMax[1]);
}
}
Python3
# Python Program to implement
# the above approach
# Function to find the minimum and
# maximum number of points included
# in a range of distance D
def minMaxRange(arr, D, N):
# Stores the minimum and maximum
# number of points that lies
# over the distance of D
Max = 1
Min = N
# Iterate the array
for i in range(N):
# Count of elements included
# to left of point at index i
dist = leftSearch(arr, arr[i] - D, i)
# Update the minimum number
# of points
Min = min(Min, dist)
# Update the maximum number
# of points
Max = max(Max, dist)
# Count of elements included
# to right of point at index i
dist = rightSearch(arr, arr[i] + D, i)
# Update the minimum number
# of points
Min = min(Min, dist)
# Update the maximum number
# of points
Max = max(Max, dist)
# Return the array
return [Min, Max]
# Function to perform the Binary
# Search to the left of arr[i]
# over the given range
def leftSearch(arr, val, i):
# Base Case
if (i == 0):
return 1
left = 0
right = i - 1
ind = -1
# Binary Search for index to left
while (left <= right):
mid = (left + right) // 2
if (arr[mid] < val):
left = mid + 1
else:
right = mid - 1
# update index
ind = mid
# Return the number of elements
# by subtracting indices
return i - ind + 1 if ind != -1 else 1
# Function to perform the Binary
# Search to the right of arr[i]
# over the given range
def rightSearch(arr, val, i):
# Base Case
if (i == len(arr) - 1):
return 1
left = i + 1
right = len(arr) - 1
ind = -1
# Binary Search for index to right
while (left <= right):
mid = (left + right) // 2
if (arr[mid] > val):
right = mid - 1
else:
left = mid + 1
# Update the index
ind = mid
# Return the number of elements
# by subtracting indices
return ind - i + 1 if ind != -1 else 1
# Driver Code
arr = [1, 3, 5, 9, 14]
N = len(arr)
D = 4
minMax = minMaxRange(arr, D, N)
# Function Call
print(f"{minMax[0]} {minMax[1]}")
# This code is contributed by gfgking
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find the minimum and
// maximum number of points included
// in a range of distance D
public static int[] minMaxRange(int[] arr, int D, int N)
{
// Stores the minimum and maximum
// number of points that lies
// over the distance of D
int max = 1, min = N;
// Iterate the array
for (int i = 0; i < N; i++)
{
// Count of elements included
// to left of point at index i
int dist = leftSearch(
arr, arr[i] - D, i);
// Update the minimum number
// of points
min = Math.Min(min, dist);
// Update the maximum number
// of points
max = Math.Max(max, dist);
// Count of elements included
// to right of point at index i
dist = rightSearch(
arr, arr[i] + D, i);
// Update the minimum number
// of points
min = Math.Min(min, dist);
// Update the maximum number
// of points
max = Math.Max(max, dist);
}
// Return the array
return new int[] { min, max };
}
// Function to perform the Binary
// Search to the left of arr[i]
// over the given range
public static int leftSearch(
int[] arr, int val, int i)
{
// Base Case
if (i == 0)
return 1;
int left = 0, right = i - 1;
int ind = -1;
// Binary Search for index to left
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] < val)
{
left = mid + 1;
}
else
{
right = mid - 1;
// update index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? i - ind + 1 : 1;
}
// Function to perform the Binary
// Search to the right of arr[i]
// over the given range
public static int rightSearch(
int[] arr, int val, int i)
{
// Base Case
if (i == arr.Length - 1)
return 1;
int left = i + 1;
int right = arr.Length - 1;
int ind = -1;
// Binary Search for index to right
while (left <= right)
{
int mid = (left + right) / 2;
if (arr[mid] > val)
{
right = mid - 1;
}
else
{
left = mid + 1;
// Update the index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? ind - i + 1 : 1;
}
// Driver Code
public static void Main()
{
int[] arr = { 1, 3, 5, 9, 14 };
int N = arr.Length;
int D = 4;
int[] minMax = minMaxRange(arr, D, N);
// Function Call
Console.Write(minMax[0] + " " + minMax[1]);
}
}
// This code is contributed by gfgking.
Javascript
<script>
// JavaScript Program to implement
// the above approach
// Function to find the minimum and
// maximum number of points included
// in a range of distance D
function minMaxRange(
arr, D, N) {
// Stores the minimum and maximum
// number of points that lies
// over the distance of D
let max = 1, min = N;
// Iterate the array
for (let i = 0; i < N; i++) {
// Count of elements included
// to left of point at index i
let dist = leftSearch(
arr, arr[i] - D, i);
// Update the minimum number
// of points
min = Math.min(min, dist);
// Update the maximum number
// of points
max = Math.max(max, dist);
// Count of elements included
// to right of point at index i
dist = rightSearch(
arr, arr[i] + D, i);
// Update the minimum number
// of points
min = Math.min(min, dist);
// Update the maximum number
// of points
max = Math.max(max, dist);
}
// Return the array
return [min, max];
}
// Function to perform the Binary
// Search to the left of arr[i]
// over the given range
function leftSearch(
arr, val, i) {
// Base Case
if (i == 0)
return 1;
let left = 0, right = i - 1;
let ind = -1;
// Binary Search for index to left
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < val) {
left = mid + 1;
}
else {
right = mid - 1;
// update index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? i - ind + 1 : 1;
}
// Function to perform the Binary
// Search to the right of arr[i]
// over the given range
function rightSearch(
arr, val, i) {
// Base Case
if (i == arr.length - 1)
return 1;
let left = i + 1;
let right = arr.length - 1;
let ind = -1;
// Binary Search for index to right
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] > val) {
right = mid - 1;
}
else {
left = mid + 1;
// Update the index
ind = mid;
}
}
// Return the number of elements
// by subtracting indices
return ind != -1 ? ind - i + 1 : 1;
}
// Driver Code
let arr = [1, 3, 5, 9, 14];
let N = arr.length;
let D = 4;
let minMax = minMaxRange(arr, D, N);
// Function Call
document.write(
minMax[0] + " " + minMax[1]);
// This code is contributed by Potta Lokesh
</script>
Producción:
1 3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por darkphoenix349 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA