Dada una array arr[] que consta de N enteros y una array query[] que consta de consultas de la forma {L, R} , la tarea de cada consulta es encontrar el mínimo de la diferencia absoluta entre elementos adyacentes en el rango [L , R] .
Ejemplos:
Entrada: arr[] = {2, 6, 1, 8, 3, 4}, query[] = {{0, 3}, {1, 5}, {4, 5}}
Salida:
4
1
1
Explicación:
Los siguientes son los valores de las consultas realizadas:
- La diferencia absoluta mínima entre elementos adyacentes en el rango [0, 3] es min(|2 – 6|, |6 – 1|, |1 – 8|) = 4.
- La diferencia absoluta mínima entre elementos adyacentes en el rango [1, 5] es min(|6 – 1|, |1 – 8|, |8 – 3|, |3 – 4| ) = 1.
- La diferencia absoluta mínima entre elementos adyacentes en el rango [4, 5] es min(|3 – 4|) = 1.
Por lo tanto, imprima 4, 1, 1 como los resultados de las consultas dadas.
Entrada: arr[] = [10, 20, 1, 1, 5 ], consulta[] = [0, 1], [1, 4], [2, 3]
Salida:
10
0
0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es crear una array diff[] que almacene la diferencia absoluta entre elementos adyacentes para cada elemento de la array. Ahora, para cada consulta, recorra la array diff[] sobre el rango [L, R – 1] e imprima el valor mínimo de todos los valores en el rango [L, R – 1] .
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;
// Structure for query range
struct Query {
int L, R;
};
int MAX = 5000;
// Function to find the minimum difference
// between adjacent array element over the
// given range [L, R] for Q Queries
void minDifference(int arr[], int n,
Query q[], int m)
{
// Find the sum of all queries
for (int i = 0; i < m; i++) {
// Left and right boundaries
// of current range
int L = q[i].L, R = q[i].R;
int ans = MAX;
for (int i = L; i < R; i++) {
ans = min(ans, arr[i]);
}
// Print the sum of the
// current query range
cout << ans << '\n';
}
}
// Function to find the minimum absolute
// difference of adjacent array elements
// for the given range
void minimumDifference(int arr[], Query q[],
int N, int m)
{
// Stores the absolute difference of
// adjacent elements
int diff[N];
for (int i = 0; i < N - 1; i++)
diff[i] = abs(arr[i] - arr[i + 1]);
// Find the minimum difference of
// adjacent elements
minDifference(diff, N - 1, q, m);
}
// Driver Code
int main()
{
int arr[] = { 2, 6, 1, 8, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
Query Q[] = { { 0, 3 }, { 1, 5 }, { 4, 5 } };
int M = sizeof(Q) / sizeof(Q[0]);
minimumDifference(arr, Q, N, M);
return 0;
}
Java
// Java program for the above approach
class GFG{
// Structure for query range
static class Query {
int L, R;
public Query(int l, int r) {
super();
L = l;
R = r;
}
};
static int MAX = 5000;
// Function to find the minimum difference
// between adjacent array element over the
// given range [L, R] for Q Queries
static void minDifference(int arr[], int n,
Query q[], int m)
{
// Find the sum of all queries
for (int i = 0; i < m; i++) {
// Left and right boundaries
// of current range
int L = q[i].L, R = q[i].R;
int ans = MAX;
for (int j = L; j < R; j++) {
ans = Math.min(ans, arr[j]);
}
// Print the sum of the
// current query range
System.out.println(ans);
}
}
// Function to find the minimum absolute
// difference of adjacent array elements
// for the given range
static void minimumDifference(int arr[], Query q[],
int N, int m)
{
// Stores the absolute difference of
// adjacent elements
int []diff = new int[N];
for (int i = 0; i < N - 1; i++)
diff[i] = Math.abs(arr[i] - arr[i + 1]);
// Find the minimum difference of
// adjacent elements
minDifference(diff, N - 1, q, m);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 6, 1, 8, 3, 4 };
int N = arr.length;
Query Q[] = {new Query( 0, 3 ),new Query( 1, 5 ),new Query( 4, 5 ) };
int M = Q.length;
minimumDifference(arr, Q, N, M);
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program for the above approach MAX = 5000; # Function to find the minimum difference # between adjacent array element over the # given range [L, R] for Q Queries def minDifference(arr, n, q, m) : # Find the sum of all queries for i in range(m) : # Left and right boundaries # of current range L = q[i][0]; R = q[i][1]; ans = MAX; for i in range(L, R) : ans = min(ans, arr[i]); # Print the sum of the # current query range print(ans); # Function to find the minimum absolute # difference of adjacent array elements # for the given range def minimumDifference(arr, q, N, m) : # Stores the absolute difference of # adjacent elements diff = [0]*N; for i in range(N - 1) : diff[i] = abs(arr[i] - arr[i + 1]); # Find the minimum difference of # adjacent elements minDifference(diff, N - 1, q, m); # Driver Code if __name__ == "__main__" : arr = [ 2, 6, 1, 8, 3, 4 ]; N = len(arr); Q = [ [ 0, 3 ], [ 1, 5 ], [ 4, 5 ] ]; M = len(Q); minimumDifference(arr, Q, N, M); # This code is contributed by AnkThon
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG{
// Structure for query range
class Query {
public int L, R;
public Query(int l, int r) {
this.L = l;
this.R = r;
}
};
static int MAX = 5000;
// Function to find the minimum difference
// between adjacent array element over the
// given range [L, R] for Q Queries
static void minDifference(int []arr, int n,
Query []q, int m)
{
// Find the sum of all queries
for (int i = 0; i < m; i++) {
// Left and right boundaries
// of current range
int L = q[i].L, R = q[i].R;
int ans = MAX;
for (int j = L; j < R; j++) {
ans = Math.Min(ans, arr[j]);
}
// Print the sum of the
// current query range
Console.WriteLine(ans);
}
}
// Function to find the minimum absolute
// difference of adjacent array elements
// for the given range
static void minimumDifference(int []arr, Query []q,
int N, int m)
{
// Stores the absolute difference of
// adjacent elements
int []diff = new int[N];
for (int i = 0; i < N - 1; i++)
diff[i] = Math.Abs(arr[i] - arr[i + 1]);
// Find the minimum difference of
// adjacent elements
minDifference(diff, N - 1, q, m);
}
// Driver Code
public static void Main()
{
int []arr = { 2, 6, 1, 8, 3, 4 };
int N = arr.Length;
Query []Q = {new Query( 0, 3 ),new Query( 1, 5 ),new Query( 4, 5 ) };
int M = Q.Length;
minimumDifference(arr, Q, N, M);
}
}
// This code is contributed by SURENDRA_GANGWAR.
Javascript
<script>
// JavaScript program for the above approach;
let MAX = 5000;
// Function to find the minimum difference
// between adjacent array element over the
// given range [L, R] for Q Queries
function minDifference(arr, n, q, m)
{
// Find the sum of all queries
for (let i = 0; i < m; i++) {
// Left and right boundaries
// of current range
let L = q[i][0], R = q[i][1];
let ans = MAX;
for (let i = L; i < R; i++) {
ans = Math.min(ans, arr[i]);
}
// Print the sum of the
// current query range
document.write(ans+'<br>');
}
}
// Function to find the minimum absolute
// difference of adjacent array elements
// for the given range
function minimumDifference(arr, q, N, m) {
// Stores the absolute difference of
// adjacent elements
let diff = new Array(N);
for (let i = 0; i < N - 1; i++)
diff[i] = Math.abs(arr[i] - arr[i + 1]);
// Find the minimum difference of
// adjacent elements
minDifference(diff, N - 1, q, m);
}
// Driver Code
let arr = [2, 6, 1, 8, 3, 4];
let N = arr.length;
let Q = [[0, 3], [1, 5], [4, 5]];
let M = Q.length;
minimumDifference(arr, Q, N, M);
//This code is contributed by Potta Lokesh
</script>
Producción:
4 1 1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la tabla dispersa que admite consultas en tiempo constante O(1) con espacio adicional O(N log N) . En lugar de pasar original arr[], pase diff[] para obtener la respuesta requerida. Siga los pasos a continuación para resolver el problema:
- Inicialice una búsqueda de array global [][] para la array dispersa.
- Defina una función preprocess(arr, N) y realice las siguientes operaciones:
- Itere sobre el rango [0, N) usando la variable i y establezca el valor de lookup[i][0] como i .
- Iterar sobre el rango [1, N) usando las variables j e i anidadas y si arr[buscar[i][j-1]] es menor que arr[buscar[i + (1 << (j-1))] [j-1] , luego configure lookup[i][j] como lookup[i][j-1] , de lo contrario, configure lookup[i][j] como lookup[i + (1 << (j – 1)) ][j – 1] .
- Defina una consulta de función (int arr[], int L, int M) y realice las siguientes operaciones:
- Inicialice la variable j como (int)log2(R – L + 1) .
- Si arr[buscar[L][j]] es menor que arr[buscar[R – (1 << j) + 1][j]], entonces devuelve arr[buscar[L][j]], de lo contrario return arr[buscar[R – (1 << j) + 1][j]] .
- Defina una función Min_difference(arr, n, q, m) y realice las siguientes operaciones:
- Llame a la función preprocess(arr, n) para preprocesar la array dispersa.
- Recorra la array dada de consultas Q[] y el valor devuelto por la función query(arr, L, R – 1) da el resultado de la consulta actual.
- Inicialice una array diff[] de tamaño N y almacene las diferencias absolutas de arr[i]-arr[i+1] para cada valor de i .
- Llame a la función Min_difference(diff, N-1, q, m) para encontrar la diferencia absoluta mínima para cada consulta.
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;
#define MAX 500
// Stores the index for the minimum
// value in the subarray arr[i, j]
int lookup[MAX][MAX];
// Structure for query range
struct Query {
int L, R;
};
// Function to fill the lookup array
// lookup[][] in the bottom up manner
void preprocess(int arr[], int n)
{
// Initialize M for the intervals
// with length 1
for (int i = 0; i < n; i++)
lookup[i][0] = i;
// Find the values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++) {
// Compute minimum value for
// all intervals with size 2^j
for (int i = 0; (i + (1 << j) - 1) < n; i++) {
// For arr[2][10], compare
// arr[lookup[0][3]] and
// arr[lookup[3][3]]
if (arr[lookup[i][j - 1]]
< arr[lookup[i + (1 << (j - 1))][j - 1]])
lookup[i][j] = lookup[i][j - 1];
// Otherwise
else
lookup[i][j]
= lookup[i + (1 << (j - 1))][j - 1];
}
}
}
// Function find minimum of absolute
// difference of all adjacent element
// in subarray arr[L..R]
int query(int arr[], int L, int R)
{
// For [2, 10], j = 3
int j = (int)log2(R - L + 1);
// For [2, 10], compare arr[lookup[0][3]]
// and arr[lookup[3][3]],
if (arr[lookup[L][j]]
<= arr[lookup[R - (1 << j) + 1][j]])
return arr[lookup[L][j]];
else
return arr[lookup[R - (1 << j) + 1][j]];
}
// Function to find the minimum of the
// ranges for M queries
void Min_difference(int arr[], int n,
Query q[], int m)
{
// Fills table lookup[n][Log n]
preprocess(arr, n);
// Compute sum of all queries
for (int i = 0; i < m; i++) {
// Left and right boundaries
// of current range
int L = q[i].L, R = q[i].R;
// Print sum of current query range
cout << query(arr, L, R - 1) << '\n';
}
}
// Function to find the minimum absolute
// difference in a range
void minimumDifference(int arr[], Query q[],
int N, int m)
{
// diff[] is to stores the absolute
// difference of adjacent elements
int diff[N];
for (int i = 0; i < N - 1; i++)
diff[i] = abs(arr[i] - arr[i + 1]);
// Call Min_difference to get minimum
// difference of adjacent elements
Min_difference(diff, N - 1, q, m);
}
// Driver Code
int main()
{
int arr[] = { 2, 6, 1, 8, 3, 4 };
int N = sizeof(arr) / sizeof(arr[0]);
Query Q[] = { { 0, 3 }, { 1, 5 }, { 4, 5 } };
int M = sizeof(Q) / sizeof(Q[0]);
minimumDifference(arr, Q, N, M);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
import javax.management.Query;
class GFG{
static final int MAX = 500;
// Stores the index for the minimum
// value in the subarray arr[i, j]
static int [][]lookup = new int[MAX][MAX];
// Structure for query range
static class Query {
int L, R;
public Query(int l, int r) {
super();
L = l;
R = r;
}
};
// Function to fill the lookup array
// lookup[][] in the bottom up manner
static void preprocess(int arr[], int n)
{
// Initialize M for the intervals
// with length 1
for (int i = 0; i < n; i++)
lookup[i][0] = i;
// Find the values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++) {
// Compute minimum value for
// all intervals with size 2^j
for (int i = 0; (i + (1 << j) - 1) < n; i++) {
// For arr[2][10], compare
// arr[lookup[0][3]] and
// arr[lookup[3][3]]
if (arr[lookup[i][j - 1]]
< arr[lookup[i + (1 << (j - 1))][j - 1]])
lookup[i][j] = lookup[i][j - 1];
// Otherwise
else
lookup[i][j]
= lookup[i + (1 << (j - 1))][j - 1];
}
}
}
// Function find minimum of absolute
// difference of all adjacent element
// in subarray arr[L..R]
static int query(int arr[], int L, int R)
{
// For [2, 10], j = 3
int j = (int)Math.log(R - L + 1);
// For [2, 10], compare arr[lookup[0][3]]
// and arr[lookup[3][3]],
if (arr[lookup[L][j]]
<= arr[lookup[R - (1 << j) + 1][j]])
return arr[lookup[L][j]];
else
return arr[lookup[R - (1 << j) + 1][j]];
}
// Function to find the minimum of the
// ranges for M queries
static void Min_difference(int arr[], int n,
Query q[], int m)
{
// Fills table lookup[n][Log n]
preprocess(arr, n);
// Compute sum of all queries
for (int i = 0; i < m; i++) {
// Left and right boundaries
// of current range
int L = q[i].L, R = q[i].R;
// Print sum of current query range
System.out.println(query(arr, L, R - 1));
}
}
// Function to find the minimum absolute
// difference in a range
static void minimumDifference(int arr[], Query q[],
int N, int m)
{
// diff[] is to stores the absolute
// difference of adjacent elements
int []diff = new int[N];
for (int i = 0; i < N - 1; i++)
diff[i] = Math.abs(arr[i] - arr[i + 1]);
// Call Min_difference to get minimum
// difference of adjacent elements
Min_difference(diff, N - 1, q, m);
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 2, 6, 1, 8, 3, 4 };
int N = arr.length;
Query Q[] = { new Query( 0, 3 ), new Query( 1, 5 ), new Query( 4, 5 ) };
int M = Q.length;
minimumDifference(arr, Q, N, M);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python program for the above approach: import math MAX = 500 ## Structure for query range class Query: def __init__(self, l, r): self.L = l self.R = r ## Function to fill the lookup array ## lookup[][] in the bottom up manner def preprocess(arr, n): ## Initialize M for the intervals ## with length 1 for i in range(n): lookup[i][0] = i; ## Find the values from smaller ## to bigger intervals j = 1 while True: if (1 << j) > n: break ## Compute minimum value for ## all intervals with size 2^j for i in range(n + 1 - (1 << j)): ## For arr[2][10], compare ## arr[lookup[0][3]] and ## arr[lookup[3][3]] if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]]): lookup[i][j] = lookup[i][j - 1]; ## Otherwise else: lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1] j+=1 ## Function find minimum of absolute ## difference of all adjacent element ## in subarray arr[L..R] def query(arr, L, R): ## For [2, 10], j = 3 j = int(math.log2(R - L + 1)) ## For [2, 10], compare arr[lookup[0][3]] ## and arr[lookup[3][3]], if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]]): return arr[lookup[L][j]] else: return arr[lookup[R - (1 << j) + 1][j]] ## Function to find the minimum of the ## ranges for M queries def Min_difference(arr, n, q, m): ## Fills table lookup[n][Log n] preprocess(arr, n) ## Compute sum of all queries for i in range(0, m): ## Left and right boundaries ## of current range L = q[i].L R = q[i].R; ## Print sum of current query range print(query(arr, L, R - 1)) ## Function to find the minimum absolute ## difference in a range def minimumDifference(arr, q, N, m): ## diff[] is to stores the absolute ## difference of adjacent elements diff = []; for i in range(N): diff.append(0) for i in range(0, N-1): diff[i] = abs(arr[i] - arr[i + 1]); ## Call Min_difference to get minimum ## difference of adjacent elements Min_difference(diff, N - 1, q, m) ## Driver code if __name__=='__main__': arr = [ 2, 6, 1, 8, 3, 4 ] N = len(arr) Q = [ Query(0, 3), Query(1, 5), Query(4, 5) ] M = len(Q) ## Stores the index for the minimum ## value in the subarray arr[i, j] global lookup lookup = [] for i in range(0, MAX): lookup.append([]) for j in range(0, MAX): lookup[i].append(0) minimumDifference(arr, Q, N, M) # This code is contributed by subhamgoyal2014.
C#
// C# program for the above approach
using System;
public class GFG{
static readonly int MAX = 500;
// Stores the index for the minimum
// value in the subarray arr[i, j]
static int [,]lookup = new int[MAX, MAX];
// Structure for query range
class Query {
public int L, R;
public Query(int l, int r) {
L = l;
R = r;
}
};
// Function to fill the lookup array
// lookup[,] in the bottom up manner
static void preprocess(int []arr, int n)
{
// Initialize M for the intervals
// with length 1
for (int i = 0; i < n; i++)
lookup[i,0] = i;
// Find the values from smaller
// to bigger intervals
for (int j = 1; (1 << j) <= n; j++) {
// Compute minimum value for
// all intervals with size 2^j
for (int i = 0; (i + (1 << j) - 1) < n; i++) {
// For arr[2,10], compare
// arr[lookup[0,3]] and
// arr[lookup[3,3]]
if (arr[lookup[i,j - 1]]
< arr[lookup[i + (1 << (j - 1)),j - 1]])
lookup[i,j] = lookup[i,j - 1];
// Otherwise
else
lookup[i,j]
= lookup[i + (1 << (j - 1)),j - 1];
}
}
}
// Function find minimum of absolute
// difference of all adjacent element
// in subarray arr[L..R]
static int query(int []arr, int L, int R)
{
// For [2, 10], j = 3
int j = (int)Math.Log(R - L + 1);
// For [2, 10], compare arr[lookup[0,3]]
// and arr[lookup[3,3]],
if (arr[lookup[L,j]]
<= arr[lookup[R - (1 << j) + 1,j]])
return arr[lookup[L,j]];
else
return arr[lookup[R - (1 << j) + 1,j]];
}
// Function to find the minimum of the
// ranges for M queries
static void Min_difference(int []arr, int n,
Query []q, int m)
{
// Fills table lookup[n,Log n]
preprocess(arr, n);
// Compute sum of all queries
for (int i = 0; i < m; i++) {
// Left and right boundaries
// of current range
int L = q[i].L, R = q[i].R;
// Print sum of current query range
Console.WriteLine(query(arr, L, R - 1));
}
}
// Function to find the minimum absolute
// difference in a range
static void minimumDifference(int []arr, Query []q,
int N, int m)
{
// diff[] is to stores the absolute
// difference of adjacent elements
int []diff = new int[N];
for (int i = 0; i < N - 1; i++)
diff[i] = Math.Abs(arr[i] - arr[i + 1]);
// Call Min_difference to get minimum
// difference of adjacent elements
Min_difference(diff, N - 1, q, m);
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 2, 6, 1, 8, 3, 4 };
int N = arr.Length;
Query []Q = { new Query( 0, 3 ), new Query( 1, 5 ), new Query( 4, 5 ) };
int M = Q.Length;
minimumDifference(arr, Q, N, M);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
let MAX = 500;
// Stores the index for the minimum
// value in the subarray arr[i, j]
let lookup = new Array(MAX).fill(0).map(() => new Array(MAX).fill(0));
// Structure for query range
class Query {
constructor(l, r) {
this.L = l;
this.R = r;
}
}
// Function to fill the lookup array
// lookup[][] in the bottom up manner
function preprocess(arr, n)
{
// Initialize M for the intervals
// with length 1
for (let i = 0; i < n; i++) lookup[i][0] = i;
// Find the values from smaller
// to bigger intervals
for (let j = 1; 1 << j <= n; j++)
{
// Compute minimum value for
// all intervals with size 2^j
for (let i = 0; i + (1 << j) - 1 < n; i++)
{
// For arr[2][10], compare
// arr[lookup[0][3]] and
// arr[lookup[3][3]]
if (arr[lookup[i][j - 1]] < arr[lookup[i + (1 << (j - 1))][j - 1]])
lookup[i][j] = lookup[i][j - 1];
// Otherwise
else lookup[i][j] = lookup[i + (1 << (j - 1))][j - 1];
}
}
}
// Function find minimum of absolute
// difference of all adjacent element
// in subarray arr[L..R]
function query(arr, L, R)
{
// For [2, 10], j = 3
let j = Math.floor(Math.log(R - L + 1));
// For [2, 10], compare arr[lookup[0][3]]
// and arr[lookup[3][3]],
if (arr[lookup[L][j]] <= arr[lookup[R - (1 << j) + 1][j]])
return arr[lookup[L][j]];
else return arr[lookup[R - (1 << j) + 1][j]];
}
// Function to find the minimum of the
// ranges for M queries
function Min_difference(arr, n, q, m)
{
// Fills table lookup[n][Log n]
preprocess(arr, n);
// Compute sum of all queries
for (let i = 0; i < m; i++)
{
// Left and right boundaries
// of current range
let L = q[i].L,
R = q[i].R;
// let sum of current query range
document.write(query(arr, L, R - 1) + "<br>");
}
}
// Function to find the minimum absolute
// difference in a range
function minimumDifference(arr, q, N, m)
{
// diff[] is to stores the absolute
// difference of adjacent elements
let diff = new Array(N);
for (let i = 0; i < N - 1; i++) diff[i] = Math.abs(arr[i] - arr[i + 1]);
// Call Min_difference to get minimum
// difference of adjacent elements
Min_difference(diff, N - 1, q, m);
}
// Driver Code
let arr = [2, 6, 1, 8, 3, 4];
let N = arr.length;
let Q = [new Query(0, 3), new Query(1, 5), new Query(4, 5)];
let M = Q.length;
minimumDifference(arr, Q, N, M);
// This code is contributed by _saurabh_jaiswal.
</script>
Producción:
4 1 1
Complejidad de tiempo: O(N*log(N))
Espacio auxiliar: O(N*N)
Publicación traducida automáticamente
Artículo escrito por ashutoshtiwari22111998 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA