Minimice el recuento de picos y valles en un arreglo determinado después de un reemplazo como máximo

Posted on by Rudeus Greyrat

Dada una array arr[] que contiene N enteros positivos, la tarea es minimizar el recuento total de picos (elementos que tienen mayor valor que ambos vecinos) y valles (elementos que tienen menos valor que ambos vecinos) reemplazando como máximo un elemento de la array dada con cualquier valor.

Nota: El primer y el último elemento de la array no pueden ser un pico o un valle, ya que no tienen dos vecinos.

Ejemplos:

Entrada: arr[] = {2, 7, 4}
Salida: 0
Explicación: La cuenta se puede convertir en 0 cambiando 7 a 3.
La array se convierte en {2, 3, 4} sin valle ni pico.

Entrada: arr[] = {1, 4, 3, 5, 3, 8}
Salida: 1
Explicación: Inicialmente el conteo total es 4. Vaya al índice 2 y cambie su valor a 5. 
Ahora la secuencia se convierte en {1, 4, 5, 5, 3, 8}.
Ahora solo un canal en el índice 4. 

 

Enfoque: El problema dado se puede resolver usando el enfoque Greedy . Observe que cualquier cambio en el i-ésimo índice afecta solo a los elementos en (i+1)-ésimo y (i-1)-ésimo índice. Siga los pasos a continuación para resolver este problema:

  • Inicialice una marca de array booleana como falsa.
  • Además, inicialice un total de variable entera como 0. Mantiene un registro del saldo general de la secuencia dada.
  • Ahora itere sobre la array dada y marque su i- ésimo índice como verdadero si el i -ésimo elemento de la array es un pico o un valle .
  • Inicializar otra variable ans como total . Mantiene la pista de la respuesta final.
  • Ahora iterar sobre la array de nuevo,
    • Supongamos que actualmente la iteración está en el índice i ,
      • Haga que el elemento en el índice i sea igual a i + 1 y actualice el saldo total de la array ahora.
      • Haga que el elemento en el índice i sea igual a i – 1 y actualice el saldo total de la array ahora.
      • El saldo total para los casos anteriores se puede lograr fácilmente mediante la creación de funciones isUp() y isDown() que comprueban que hay un pico y un valle respectivamente en un índice particular.
      • Además, actualice la variable ans en consecuencia.
  • Imprime el valor representado por ans variable.

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 check up at the index i
bool isUp(int i, int arr[], int N)
{
    return (i > 0 && i < N - 1
            && arr[i] < arr[i - 1]
            && arr[i] < arr[i + 1]);
}
 
// Function to check down at the index i
bool isDown(int i, int arr[], int N)
{
    return (i > 0 && i < N - 1
            && arr[i] > arr[i - 1]
            && arr[i] > arr[i + 1]);
}
 
// Solve function
int solve(int arr[], int N)
{
    // Initializing a boolean array
    bool mark[N] = { 0 };
 
    int total = 0;
 
    // Iterate over the array
    for (int i = 1; i < N - 1; i++) {
 
        // Peak
        if (arr[i] > arr[i + 1]
            && arr[i] > arr[i - 1]) {
            mark[i] = 1;
            total++;
        }
 
        // Trough
        else if (arr[i] < arr[i + 1]
                 && arr[i] < arr[i - 1]) {
            mark[i] = 1;
            total++;
        }
    }
 
    // Initialize ans variable as total
    int ans = total;
    for (int i = 1; i < N - 1; i++) {
 
        // Make arr[i] equal to arr[i - 1]
        int temp = arr[i];
        arr[i] = arr[i - 1];
        ans
 
            = min(
                ans,
                total - mark[i - 1] - mark[i]
                    - mark[i + 1]
                    + isUp(i - 1, arr, N)
                    + isDown(i - 1, arr, N)
                    + isUp(i, arr, N)
                    + isDown(i, arr, N)
                    + isUp(i + 1, arr, N)
                    + isDown(i + 1, arr, N));
 
        // Make arr[i] equal to arr[i + 1]
        arr[i] = arr[i + 1];
        ans
            = min(
                ans,
                total
                    - mark[i - 1] - mark[i]
                    - mark[i + 1]
                    + isUp(i - 1, arr, N)
                    + isDown(i - 1, arr, N)
                    + isUp(i, arr, N)
                    + isDown(i, arr, N)
                    + isUp(i + 1, arr, N)
                    + isDown(i + 1, arr, N));
        arr[i] = temp;
    }
 
    // Return the ans
    return ans;
}
 
// Menu driver code
int main()
{
    // Initializing an array
    int arr[] = { 1, 4, 3, 5, 3, 8 };
 
    // Size of arr
    int N = sizeof(arr) / sizeof(int);
 
    // Calling solve function
    cout << solve(arr, N);
 
    return 0;
}

Java

// Java code for the above approach
import java.util.*;
 
class GFG{
 
  // Function to check up at the index i
  static int isUp(int i, int arr[], int N)
  {
    if (i > 0 && i < N - 1
        && arr[i] < arr[i - 1]
        && arr[i] < arr[i + 1])
    {
      return 1;
    }
    else
      return 0;
  }
 
  // Function to check down at the index i
  static int isDown(int i, int arr[], int N)
  {
    if (i > 0 && i < N - 1
        && arr[i] > arr[i - 1]
        && arr[i] > arr[i + 1])
    {
      return 1;
    }
    else
      return 0;
  }
 
  // Solve function
  static int solve(int arr[], int N)
  {
    // Initializing a boolean array
    int mark[] = new int[N] ;
 
 
    int total = 0;
 
    // Iterate over the array
    for (int i = 1; i < N - 1; i++) {
 
      // Peak
      if (arr[i] > arr[i + 1]
          && arr[i] > arr[i - 1]) {
        mark[i] = 1;
        total++;
      }
 
      // Trough
      else if (arr[i] < arr[i + 1]
               && arr[i] < arr[i - 1]) {
        mark[i] = 1;
        total++;
      }
    }
 
    // Initialize ans variable as total
    int ans = total;
    for (int i = 1; i < N - 1; i++) {
 
      // Make arr[i] equal to arr[i - 1]
      int temp = arr[i];
      arr[i] = arr[i - 1];
      ans
 
        = Math.min(
        ans,
        total - mark[i - 1] - mark[i]
        - mark[i + 1]
        + isUp(i - 1, arr, N)
        + isDown(i - 1, arr, N)
        + isUp(i, arr, N)
        + isDown(i, arr, N)
        + isUp(i + 1, arr, N)
        + isDown(i + 1, arr, N));
 
      // Make arr[i] equal to arr[i + 1]
      arr[i] = arr[i + 1];
      ans
        = Math.min(
        ans,
        total
        - mark[i - 1] - mark[i]
        - mark[i + 1]
        + isUp(i - 1, arr, N)
        + isDown(i - 1, arr, N)
        + isUp(i, arr, N)
        + isDown(i, arr, N)
        + isUp(i + 1, arr, N)
        + isDown(i + 1, arr, N));
      arr[i] = temp;
    }
 
    // Return the ans
    return ans;
  }
 
  // Driver Code
  public static void main(String[] args)
  {
 
    // Initializing an array
    int arr[] = { 1, 4, 3, 5, 3, 8 };
 
    // Size of arr
    int N = arr.length;
 
    // Calling solve function
    System.out.print(solve(arr, N));
  }
}
 
// This code is contributed by sanjoy_62.

Python3

# Python program for the above approach
 
# Function to check up at the index i
def isUp (i, arr, N):
    return (i > 0 and i < N - 1
        and arr[i] < arr[i - 1]
        and arr[i] < arr[i + 1]);
 
# Function to check down at the index i
def isDown (i, arr, N):
    return (i > 0 and i < N - 1
        and arr[i] > arr[i - 1]
        and arr[i] > arr[i + 1]);
 
# Solve function
def solve (arr, N):
    # Initializing a boolean array
    mark = [0] * N
 
    total = 0;
 
    # Iterate over the array
    for i in range(1, N - 1):
 
        # Peak
        if (arr[i] > arr[i + 1] and arr[i] > arr[i - 1]):
            mark[i] = 1;
            total += 1
         
        # Trough
        elif (arr[i] < arr[i + 1]
            and arr[i] < arr[i - 1]):
            mark[i] = 1;
            total += 1
 
    # Initialize ans variable as total
    ans = total;
    for i in range(1, N - 1):
 
        # Make arr[i] equal to arr[i - 1]
        temp = arr[i];
        arr[i] = arr[i - 1];
        ans = min(
            ans,
            total - mark[i - 1] - mark[i]
            - mark[i + 1]
            + isUp(i - 1, arr, N)
            + isDown(i - 1, arr, N)
            + isUp(i, arr, N)
            + isDown(i, arr, N)
            + isUp(i + 1, arr, N)
            + isDown(i + 1, arr, N));
 
        # Make arr[i] equal to arr[i + 1]
        arr[i] = arr[i + 1];
        ans = min(
            ans,
            total
            - mark[i - 1] - mark[i]
            - mark[i + 1]
            + isUp(i - 1, arr, N)
            + isDown(i - 1, arr, N)
            + isUp(i, arr, N)
            + isDown(i, arr, N)
            + isUp(i + 1, arr, N)
            + isDown(i + 1, arr, N));
        arr[i] = temp;
     
    # Return the ans
    return ans;
 
# Menu driver code
 
# Initializing an array
arr = [1, 4, 3, 5, 3, 8];
 
# Size of arr
N = len(arr)
 
# Calling solve function
print(solve(arr, N));
 
# This code is contributed by gfgking

C#

// C# code for the above approach
using System;
 
class GFG {
 
  // Function to check up at the index i
  static int isUp(int i, int []arr, int N)
  {
    if (i > 0 && i < N - 1
        && arr[i] < arr[i - 1]
        && arr[i] < arr[i + 1])
    {
      return 1;
    }
    else
      return 0;
  }
 
  // Function to check down at the index i
  static int isDown(int i, int []arr, int N)
  {
    if (i > 0 && i < N - 1
        && arr[i] > arr[i - 1]
        && arr[i] > arr[i + 1])
    {
      return 1;
    }
    else
      return 0;
  }
 
  // Solve function
  static int solve(int []arr, int N)
  {
    // Initializing a boolean array
    int []mark = new int[N] ;
 
 
    int total = 0;
 
    // Iterate over the array
    for (int i = 1; i < N - 1; i++) {
 
      // Peak
      if (arr[i] > arr[i + 1]
          && arr[i] > arr[i - 1]) {
        mark[i] = 1;
        total++;
      }
 
      // Trough
      else if (arr[i] < arr[i + 1]
               && arr[i] < arr[i - 1]) {
        mark[i] = 1;
        total++;
      }
    }
 
    // Initialize ans variable as total
    int ans = total;
    for (int i = 1; i < N - 1; i++) {
 
      // Make arr[i] equal to arr[i - 1]
      int temp = arr[i];
      arr[i] = arr[i - 1];
      ans
 
        = Math.Min(
        ans,
        total - mark[i - 1] - mark[i]
        - mark[i + 1]
        + isUp(i - 1, arr, N)
        + isDown(i - 1, arr, N)
        + isUp(i, arr, N)
        + isDown(i, arr, N)
        + isUp(i + 1, arr, N)
        + isDown(i + 1, arr, N));
 
      // Make arr[i] equal to arr[i + 1]
      arr[i] = arr[i + 1];
      ans
        = Math.Min(
        ans,
        total
        - mark[i - 1] - mark[i]
        - mark[i + 1]
        + isUp(i - 1, arr, N)
        + isDown(i - 1, arr, N)
        + isUp(i, arr, N)
        + isDown(i, arr, N)
        + isUp(i + 1, arr, N)
        + isDown(i + 1, arr, N));
      arr[i] = temp;
    }
 
    // Return the ans
    return ans;
  }
 
  // Driver Code
  public static void Main()
  {
 
    // Initializing an array
    int []arr = { 1, 4, 3, 5, 3, 8 };
 
    // Size of arr
    int N = arr.Length;
 
    // Calling solve function
    Console.Write(solve(arr, N));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

Javascript

<script>
    // JavaScript program for the above approach
 
    // Function to check up at the index i
    const isUp = (i, arr, N) => {
        return (i > 0 && i < N - 1
            && arr[i] < arr[i - 1]
            && arr[i] < arr[i + 1]);
    }
 
    // Function to check down at the index i
    const isDown = (i, arr, N) => {
        return (i > 0 && i < N - 1
            && arr[i] > arr[i - 1]
            && arr[i] > arr[i + 1]);
    }
 
    // Solve function
    const solve = (arr, N) => {
        // Initializing a boolean array
        let mark = new Array(N).fill(0);
 
        let total = 0;
 
        // Iterate over the array
        for (let i = 1; i < N - 1; i++) {
 
            // Peak
            if (arr[i] > arr[i + 1]
                && arr[i] > arr[i - 1]) {
                mark[i] = 1;
                total++;
            }
 
            // Trough
            else if (arr[i] < arr[i + 1]
                && arr[i] < arr[i - 1]) {
                mark[i] = 1;
                total++;
            }
        }
 
        // Initialize ans variable as total
        let ans = total;
        for (let i = 1; i < N - 1; i++) {
 
            // Make arr[i] equal to arr[i - 1]
            let temp = arr[i];
            arr[i] = arr[i - 1];
            ans = Math.min(
                ans,
                total - mark[i - 1] - mark[i]
                - mark[i + 1]
                + isUp(i - 1, arr, N)
                + isDown(i - 1, arr, N)
                + isUp(i, arr, N)
                + isDown(i, arr, N)
                + isUp(i + 1, arr, N)
                + isDown(i + 1, arr, N));
 
            // Make arr[i] equal to arr[i + 1]
            arr[i] = arr[i + 1];
            ans = Math.min(
                ans,
                total
                - mark[i - 1] - mark[i]
                - mark[i + 1]
                + isUp(i - 1, arr, N)
                + isDown(i - 1, arr, N)
                + isUp(i, arr, N)
                + isDown(i, arr, N)
                + isUp(i + 1, arr, N)
                + isDown(i + 1, arr, N));
            arr[i] = temp;
        }
 
        // Return the ans
        return ans;
    }
 
    // Menu driver code
 
    // Initializing an array
    let arr = [1, 4, 3, 5, 3, 8];
 
    // Size of arr
    let N = arr.length;
 
    // Calling solve function
    document.write(solve(arr, N));
 
// This code is contributed by rakeshsahni
 
</script>
Producción

1

Complejidad temporal: O(N)
Espacio auxiliar: O(N)

Publicación traducida automáticamente

Artículo escrito por bhuwanesh y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *