Dada una array arr , la tarea es reemplazar cada elemento de la array por el máximo de K elementos siguientes y K anteriores.
Ejemplo:
Entrada: arr[] = {12, 5, 3, 9, 21, 36, 17}, K=2
Salida: 5 12 21 36 36 21 36Entrada: arr[] = { 13, 21, 19}, K=1
Salida: 21, 19, 21
Enfoque ingenuo: siga los pasos a continuación para resolver este problema:
- Recorra la array de i=0 a i<N y para cada elemento:
- Ejecute otro bucle de j=iK a j<=i+K y cambie arr[i] al máximo de K elementos siguientes y K anteriores.
- Imprima la array después de que finalice el ciclo anterior.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <iostream>
#include <limits.h>
#include <math.h>
using namespace std;
// Function to update the array
// arr[i] = maximum of prev K and next K elements.
void updateArray(int arr[], int N, int K)
{
int start, end;
for (int i = 0; i < N; i++) {
int mx = INT_MIN;
// Start limit is max(i-K, 0)
start = max(i - K, 0);
// End limit in min(i+K, N-1)
end = min(i + K, N - 1);
for (int j = start; j <= end; j++) {
// Skipping the current element
if (j == i) {
continue;
}
mx = max(arr[j], mx);
}
cout << mx << ' ';
}
}
// Driver Code
int main()
{
int arr[] = { 12, 5, 3, 9, 21, 36, 17 };
int N = sizeof(arr) / sizeof(arr[0]);
int K = 2;
updateArray(arr, N, K);
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to update the array arr[i] = maximum
// of prev K and next K elements.
static void updateArray(int arr[], int N, int K)
{
int start, end;
for(int i = 0; i < N; i++)
{
int mx = Integer.MIN_VALUE;
// Start limit is max(i-K, 0)
start = Math.max(i - K, 0);
// End limit in min(i+K, N-1)
end = Math.min(i + K, N - 1);
for(int j = start; j <= end; j++)
{
// Skipping the current element
if (j == i)
{
continue;
}
mx = Math.max(arr[j], mx);
}
System.out.print(mx + " ");
}
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 12, 5, 3, 9, 21, 36, 17 };
int N = arr.length;
int K = 2;
updateArray(arr, N, K);
}
}
// This code is contributed by Samim Hossain Mondal.
Python3
# python3 program for the above approach INT_MIN = -2147483648 # Function to update the array # arr[i] = maximum of prev K and next K elements. def updateArray(arr, N, K): for i in range(0, N): mx = INT_MIN # Start limit is max(i-K, 0) start = max(i - K, 0) # End limit in min(i+K, N-1) end = min(i + K, N - 1) for j in range(start, end + 1): # Skipping the current element if (j == i): continue mx = max(arr[j], mx) print(mx, end=" ") # Driver Code if __name__ == "__main__": arr = [12, 5, 3, 9, 21, 36, 17] N = len(arr) K = 2 updateArray(arr, N, K) # This code is contributed by rakeshsahni
C#
// C# program for the above approach
using System;
class GFG
{
// Function to update the array arr[i] = maximum
// of prev K and next K elements.
static void updateArray(int[] arr, int N, int K)
{
int start, end;
for (int i = 0; i < N; i++)
{
int mx = int.MinValue;
// Start limit is max(i-K, 0)
start = Math.Max(i - K, 0);
// End limit in min(i+K, N-1)
end = Math.Min(i + K, N - 1);
for (int j = start; j <= end; j++)
{
// Skipping the current element
if (j == i)
{
continue;
}
mx = Math.Max(arr[j], mx);
}
Console.Write(mx + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 12, 5, 3, 9, 21, 36, 17 };
int N = arr.Length;
int K = 2;
updateArray(arr, N, K);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript code for the above approach
// Function to update the array
// arr[i] = maximum of prev K and next K elements.
function updateArray(arr, N, K) {
let start, end;
for (let i = 0; i < N; i++) {
let mx = Number.MIN_VALUE;
// Start limit is max(i-K, 0)
start = Math.max(i - K, 0);
// End limit in min(i+K, N-1)
end = Math.min(i + K, N - 1);
for (let j = start; j <= end; j++) {
// Skipping the current element
if (j == i) {
continue;
}
mx = Math.max(arr[j], mx);
}
document.write(mx + ' ')
}
}
// Driver Code
let arr = [12, 5, 3, 9, 21, 36, 17];
let N = arr.length;
let K = 2;
updateArray(arr, N, K);
// This code is contributed by Potta Lokesh
</script>
Producción
5 12 21 36 36 21 36
Complejidad temporal: O(N*N)
Espacio auxiliar: O(1)
Enfoque eficiente: se puede usar un árbol de segmentos para resolver este problema. Por lo tanto, construya un árbol de segmento máximo de rango, donde:
- Los Nodes hoja son los elementos de la array de entrada.
- Cada Node interno representa el máximo de todos sus hijos.
Ahora, después de construir el árbol de segmentos, encuentre el máximo de (iK) a (i-1) , digamos a la izquierda y el máximo de (i+1) a (i+K) , digamos a la derecha usando la consulta en este árbol de segmentos. Reemplace arr[i] con el máximo de left y right .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code for the above approach
#define MAXN 500001
#include <bits/stdc++.h>
using namespace std;
// Function to build the tree
void buildTree(vector<int>& arr,
vector<int>& tree, int s,
int e, int index)
{
// Leaf Node
if (s == e) {
tree[index] = arr[s];
return;
}
// Finding mid
int mid = (s + e) / 2;
buildTree(arr, tree, s,
mid, 2 * index + 1);
buildTree(arr, tree, mid + 1,
e, 2 * index + 2);
// Updating current node
// by the maximum of its children
tree[index]
= max(tree[2 * index + 1],
tree[2 * index + 2]);
}
// Function to find the maximum
// element in a given range
int query(vector<int>& tree, int s,
int e, int index, int l,
int r)
{
if (l > e or r < s) {
return INT_MIN;
}
if (l <= s and r >= e) {
return tree[index];
}
int mid = (s + e) / 2;
int left = query(tree, s, mid,
2 * index + 1, l, r);
int right
= query(tree, mid + 1, e,
2 * index + 2, l, r);
return max(left, right);
}
// Function to replace each array element by
// the maximum of K next and K previous elements
void updateArray(vector<int>& arr, int K)
{
// To store the segment tree
vector<int> tree(MAXN);
int N = arr.size();
buildTree(arr, tree, 0, N - 1, 0);
for (int i = 0; i < N; ++i) {
// For 0th index only find
// the maximum out of 1 to i+K
if (i == 0) {
cout << query(tree, 0, N - 1, 0, 1,
min(i + K, N - 1))
<< ' ';
continue;
}
// For (N-1)th index only find
// the maximum out of 0 to (N-2)
if (i == N - 1) {
cout << query(tree, 0, N - 1,
0, max(0, i - K),
N - 2);
continue;
}
// Maximum from (i-K) to (i-1)
int left = query(tree, 0, N - 1,
0, max(i - K, 0),
i - 1);
// Maximum from (i+1) to (i+K)
int right = query(tree, 0,
N - 1, 0, i + 1,
min(i + K, N - 1));
cout << max(left, right) << ' ';
}
}
// Driver Code
int main()
{
vector<int> arr = { 12, 5, 3, 9,
21, 36, 17 };
int K = 2;
updateArray(arr, K);
}
Java
// Java code for the above approach
import java.io.*;
class GFG {
static int MAXN = 500001;
// Function to build the tree
static void buildTree(int[] arr, int[] tree, int s,
int e, int index)
{
// Leaf Node
if (s == e) {
tree[index] = arr[s];
return;
}
// Finding mid
int mid = (s + e) / 2;
buildTree(arr, tree, s, mid, 2 * index + 1);
buildTree(arr, tree, mid + 1, e, 2 * index + 2);
// Updating current node
// by the maximum of its children
tree[index] = Math.max(tree[2 * index + 1],
tree[2 * index + 2]);
}
// Function to find the maximum
// element in a given range
static int query(int[] tree, int s, int e, int index,
int l, int r)
{
if (l > e || r < s) {
return Integer.MIN_VALUE;
}
if (l <= s && r >= e) {
return tree[index];
}
int mid = (s + e) / 2;
int left = query(tree, s, mid, 2 * index + 1, l, r);
int right
= query(tree, mid + 1, e, 2 * index + 2, l, r);
return Math.max(left, right);
}
// Function to replace each array element by
// the maximum of K next and K previous elements
static void updateArray(int[] arr, int K)
{
// To store the segment tree
int[] tree = new int[MAXN];
int N = arr.length;
buildTree(arr, tree, 0, N - 1, 0);
for (int i = 0; i < N; ++i)
{
// For 0th index only find
// the maximum out of 1 to i+K
if (i == 0) {
System.out.print(query(tree, 0, N - 1, 0, 1,
Math.min(i + K, N - 1))
+ " ");
continue;
}
// For (N-1)th index only find
// the maximum out of 0 to (N-2)
if (i == N - 1) {
System.out.println(query(tree, 0, N - 1, 0,
Math.max(0, i - K),
N - 2));
continue;
}
// Maximum from (i-K) to (i-1)
int left = query(tree, 0, N - 1, 0,
Math.max(i - K, 0), i - 1);
// Maximum from (i+1) to (i+K)
int right = query(tree, 0, N - 1, 0, i + 1,
Math.min(i + K, N - 1));
System.out.print(Math.max(left, right) + " ");
}
}
// Driver Code
public static void main (String[] args)
{
int[] arr = { 12, 5, 3, 9, 21, 36, 17 };
int K = 2;
updateArray(arr, K);
}
}
// This code is contributed by Shubham Singh.
Python3
# Python code for the above approach import sys MAXN = 500001 # Function to build the tree def buildTree(arr, tree, s, e, index): # Leaf Node if (s == e): tree[index] = arr[s] return # Finding mid mid = (s + e) // 2 buildTree(arr, tree, s, mid, 2 * index + 1) buildTree(arr, tree, mid + 1, e, 2 * index + 2) # Updating current node # by the maximum of its children tree[index] = max(tree[2 * index + 1], tree[2 * index + 2]) # Function to find the maximum # element in a given range def query(tree, s, e, index, l, r): if (l > e or r < s): return -sys.maxsize -1 if (l <= s and r >= e): return tree[index] mid = (s + e) // 2 left = query(tree, s, mid,2 * index + 1, l, r) right = query(tree, mid + 1, e, 2 * index + 2, l, r) return max(left, right) # Function to replace each array element by # the maximum of K next and K previous elements def updateArray(arr, K): global MAXN # To store the segment tree tree = [0 for i in range(MAXN)] N = len(arr) buildTree(arr, tree, 0, N - 1, 0) for i in range(N): # For 0th index only find # the maximum out of 1 to i+K if (i == 0): print(query(tree, 0, N - 1, 0, 1, min(i + K, N - 1)),end = ' ') continue # For (N-1)th index only find # the maximum out of 0 to (N-2) if (i == N - 1): print(query(tree, 0, N - 1, 0, max(0, i - K), N - 2)) continue # Maximum from (i-K) to (i-1) left = query(tree, 0, N - 1, 0, max(i - K, 0), i - 1) # Maximum from (i+1) to (i+K) right = query(tree, 0, N - 1, 0, i + 1, min(i + K, N - 1)) print(max(left, right),end = ' ') # Driver Code arr = [12, 5, 3, 9, 21, 36, 17] K = 2 updateArray(arr, K) # This code is contributed by shinjanpatra
C#
// C# code for the above approach
using System;
class GFG {
static int MAXN = 500001;
// Function to build the tree
static void buildTree(int[] arr, int[] tree, int s,
int e, int index)
{
// Leaf Node
if (s == e) {
tree[index] = arr[s];
return;
}
// Finding mid
int mid = (s + e) / 2;
buildTree(arr, tree, s, mid, 2 * index + 1);
buildTree(arr, tree, mid + 1, e, 2 * index + 2);
// Updating current node
// by the maximum of its children
tree[index] = Math.Max(tree[2 * index + 1],
tree[2 * index + 2]);
}
// Function to find the maximum
// element in a given range
static int query(int[] tree, int s, int e, int index,
int l, int r)
{
if (l > e || r < s) {
return Int32.MinValue;
}
if (l <= s && r >= e) {
return tree[index];
}
int mid = (s + e) / 2;
int left = query(tree, s, mid, 2 * index + 1, l, r);
int right
= query(tree, mid + 1, e, 2 * index + 2, l, r);
return Math.Max(left, right);
}
// Function to replace each array element by
// the maximum of K next and K previous elements
static void updateArray(int[] arr, int K)
{
// To store the segment tree
int[] tree = new int[MAXN];
int N = arr.Length;
buildTree(arr, tree, 0, N - 1, 0);
for (int i = 0; i < N; ++i) {
// For 0th index only find
// the maximum out of 1 to i+K
if (i == 0) {
Console.Write(query(tree, 0, N - 1, 0, 1,
Math.Min(i + K, N - 1))
+ " ");
continue;
}
// For (N-1)th index only find
// the maximum out of 0 to (N-2)
if (i == N - 1) {
Console.Write(query(tree, 0, N - 1, 0,
Math.Max(0, i - K),
N - 2));
continue;
}
// Maximum from (i-K) to (i-1)
int left = query(tree, 0, N - 1, 0,
Math.Max(i - K, 0), i - 1);
// Maximum from (i+1) to (i+K)
int right = query(tree, 0, N - 1, 0, i + 1,
Math.Min(i + K, N - 1));
Console.Write(Math.Max(left, right) + " ");
}
}
// Driver Code
public static void Main()
{
int[] arr = { 12, 5, 3, 9, 21, 36, 17 };
int K = 2;
updateArray(arr, K);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript code for the above approach
let MAXN = 500001
// Function to build the tree
function buildTree(arr, tree, s, e, index) {
// Leaf Node
if (s == e) {
tree[index] = arr[s];
return;
}
// Finding mid
let mid = Math.floor((s + e) / 2);
buildTree(arr, tree, s, mid, 2 * index + 1);
buildTree(arr, tree, mid + 1, e, 2 * index + 2);
// Updating current node
// by the maximum of its children
tree[index] = Math.max(tree[2 * index + 1], tree[2 * index + 2]);
}
// Function to find the maximum
// element in a given range
function query(tree, s, e, index, l, r) {
if (l > e || r < s) {
return Number.MIN_SAFE_INTEGER;
}
if (l <= s && r >= e) {
return tree[index];
}
let mid = Math.floor((s + e) / 2);
let left = query(tree, s, mid,
2 * index + 1, l, r);
let right = query(tree, mid + 1, e, 2 * index + 2, l, r);
return Math.max(left, right);
}
// Function to replace each array element by
// the maximum of K next and K previous elements
function updateArray(arr, K) {
// To store the segment tree
let tree = new Array(MAXN).fill(0);
let N = arr.length;
buildTree(arr, tree, 0, N - 1, 0);
for (let i = 0; i < N; ++i) {
// For 0th index only find
// the maximum out of 1 to i+K
if (i == 0) {
document.write(query(tree, 0, N - 1, 0, 1, Math.min(i + K, N - 1)) + ' ');
continue;
}
// For (N-1)th index only find
// the maximum out of 0 to (N-2)
if (i == N - 1) {
document.write(query(tree, 0, N - 1, 0, Math.max(0, i - K), N - 2));
continue;
}
// Maximum from (i-K) to (i-1)
let left = query(tree, 0, N - 1, 0, Math.max(i - K, 0), i - 1);
// Maximum from (i+1) to (i+K)
let right = query(tree, 0, N - 1, 0, i + 1, Math.min(i + K, N - 1));
document.write(Math.max(left, right) + ' ');
}
}
// Driver Code
let arr = [12, 5, 3, 9, 21, 36, 17];
let K = 2;
updateArray(arr, K);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
5 12 21 36 36 21 36
Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por pintusaini y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA