Recuento del rango de índice [L, R] en Array de modo que al eliminar todas sus instancias se ordena el Array

Dada una array arr[] de longitud N, la tarea es encontrar el número de buenos rangos en la array arr[].

Un buen rango se define como el rango de los índices izquierdo y derecho, es decir, [L. R] en la array arr[]  de manera que al eliminar todos los números en el rango [L, R] de la array arr[]  y las apariencias de esos elementos fuera del rango, la array arr[]  se ordena en forma no decreciente ordenar _

Ejemplo:

Entrada: N=3, arr[] = {9, 8, 7}
Salida: 3
Explicación: Los buenos rangos son: (2, 3), (1, 3), (1, 2).
(2, 3) es un buen rango ya que la array resultante [9] está ordenada (eliminamos 8, 7).
(1, 3) es un buen rango ya que la array resultante [] está ordenada (eliminamos 9, 8, 7)
(1, 2) es un buen rango ya que la array resultante [7] está ordenada (eliminamos 9, 8) .

Entrada: N=5, arr[] = {5, 3, 1, 5, 2}
Salida: 7
Explicación: Los buenos rangos son: (1, 2), (1, 3), (1, 4), ( 1, 5), (2, 4), (2, 5), (3, 5).
(1, 2) es un buen rango ya que la array resultante [1, 2] está ordenada 
(1, 3) es un buen rango ya que la array resultante [2] está ordenada 
(1, 4) es un buen rango ya que la array resultante la array [2] está ordenada 
(1, 5) es un buen rango ya que la array resultante [] está ordenada 
(2, 4) es un buen rango ya que la array resultante [2] está ordenada 
(2, 5) es un buen rango como la array resultante [] está ordenada 
(3, 5) es un buen rango ya que la array resultante [3] está ordenada 

Enfoque: el enfoque consiste en encontrar cada subarreglo [l, r] y comprobar si el resto del conjunto está ordenado o no. Si la array está ordenada, entonces, con la parte izquierda del rango en l y la parte derecha desde r hasta el final, cada subarreglo será la respuesta. A continuación se muestra la implementación del enfoque anterior:

  • Inicialice la variable count como 0 para almacenar el número de dichos subarreglos .
  • Defina una función chk_sorted(l, r, a) para verificar si la array restante a[] está ordenada o no:
  • Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
    • Iterar sobre el rango [i+1, N] usando la variable i y realizar los siguientes pasos:
      • Llame a la función chk_sorted(i, j, a) y, si la función devuelve verdadero , aumente el valor de count en len(a)-j y rompa el bucle .
  • Devuelve el valor de count como respuesta.

A continuación se muestra la implementación del enfoque anterior.

C++

// C++ program to implement the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to chk array is sorted or not
bool chk_sorted(int l, int r, vector<int> a)
{
     
    // Taking range element separately
    // to be removed
    vector<int> temp;
    unordered_set<int> s;
    for(int i = l; i <= r; i++)
    {
        temp.push_back(a[i]);
        s.insert(a[i]);
    }
 
    vector<int> chk;
    for(int i = 0; i < a.size(); i++)
    {
         
        // Checking is all range element
        // occurrence is removed
        if (s.find(a[i]) == s.end())
        {
            chk.push_back(a[i]);
        }
    }
 
    vector<int> chk1 = chk;
 
    sort(chk1.begin(), chk1.end());
 
    // If array is sorted return true
    for(int i = 0; i < chk.size(); i++)
    {
        if (chk[i] != chk1[i])
        {
            return false;
        }
    }
    return true;
}
 
// Function to count all good ranges
int countp(vector<int> a)
{
     
    // Initial count 0
    int count = 0;
 
    // Nested loop implementation
    for(int i = 0; i < a.size(); i++)
    {
        for(int j = i + 1; j < a.size(); j++)
        {
             
            // Checking if range is good
            if (chk_sorted(i, j, a))
            {
                 
                // According to observation as given
                // in approach
                count += a.size() - j;
                break;
            }
        }
    }
    return count;
}
 
// Driver code
int main()
{
    int N = 5;
    vector<int> A = { 5, 3, 1, 5, 2 };
     
    cout << (countp(A));
}
 
// This code is contributed by Potta Lokesh

Java

// Java program to implement the above approach
import java.util.*;
 
class GFG{
 
// Function to chk array is sorted or not
static boolean chk_sorted(int l, int r, int []a)
{
     
    // Taking range element separately
    // to be removed
    Vector<Integer> temp = new Vector<Integer>();
    HashSet<Integer> s = new HashSet<Integer>();
    for(int i = l; i <= r; i++)
    {
        temp.add(a[i]);
        s.add(a[i]);
    }
 
    Vector<Integer> chk=new Vector<Integer>();
    for(int i = 0; i < a.length; i++)
    {
         
        // Checking is all range element
        // occurrence is removed
        if (!s.contains(a[i]))
        {
            chk.add(a[i]);
        }
    }
 
    Vector<Integer> chk1 = new Vector<Integer>(chk);
 
    Collections.sort(chk1);
 
    // If array is sorted return true
    for(int i = 0; i < chk.size(); i++)
    {
        if (chk.get(i) != chk1.get(i))
        {
            return false;
        }
    }
    return true;
}
 
// Function to count all good ranges
static int countp(int []a)
{
     
    // Initial count 0
    int count = 0;
 
    // Nested loop implementation
    for(int i = 0; i < a.length; i++)
    {
        for(int j = i + 1; j < a.length; j++)
        {
             
            // Checking if range is good
            if (chk_sorted(i, j, a))
            {
                 
                // According to observation as given
                // in approach
                count += a.length - j;
                break;
            }
        }
    }
    return count;
}
 
// Driver code
public static void main(String[] args)
{
    int N = 5;
    int [] A = { 5, 3, 1, 5, 2 };
     
    System.out.print(countp(A));
}
}
// This code is contributed by shikhasingrajput

Python3

# Python program to implement the above approach
 
# function to chk array is sorted or not
def chk_sorted(l, r, a):
 
    # taking range element separately
    # to be removed
    l = list(a[l:r + 1])
 
    chk = []
    for i in a:
        # checking is all range element
        # occurrence is removed
        if(i not in l):
            chk.append(i)
    chk1 = list(chk)
    chk1.sort()
    # if array is sorted return true
    if(chk1 == chk):
        return True
    else:
        return False
 
 
# function to count all good ranges
def countp(a):
 
    # initial count 0
    count = 0
 
    # nested loop implementation
    for i in range(len(a)):
        for j in range(i + 1, len(a)):
 
            # checking if range is good
            if(chk_sorted(i, j, a)):
 
                # according to observation as given
                # in approach
                count += len(a)-j
                break
    return count
 
 
# Driver code
N = 5
A = [5, 3, 1, 5, 2]
print(countp(A))

C#

// C# program to implement the above approach
using System;
using System.Collections.Generic;
 
class GFG {
 
    // Function to chk array is sorted or not
    static bool chk_sorted(int l, int r, int[] a)
    {
 
        // Taking range element separately
        // to be removed
        List<int> temp = new List<int>();
        HashSet<int> s = new HashSet<int>();
        for (int i = l; i <= r; i++) {
            temp.Add(a[i]);
            s.Add(a[i]);
        }
 
        List<int> chk = new List<int>();
        for (int i = 0; i < a.Length; i++) {
 
            // Checking is all range element
            // occurrence is removed
            if (!s.Contains(a[i])) {
                chk.Add(a[i]);
            }
        }
 
        List<int> chk1 = new List<int>(chk);
 
        chk1.Sort();
 
        // If array is sorted return true
        for (int i = 0; i < chk.Count; i++) {
            if (chk[i] != chk1[i]) {
                return false;
            }
        }
        return true;
    }
 
    // Function to count all good ranges
    static int countp(int[] a)
    {
 
        // Initial count 0
        int count = 0;
 
        // Nested loop implementation
        for (int i = 0; i < a.Length; i++) {
            for (int j = i + 1; j < a.Length; j++) {
 
                // Checking if range is good
                if (chk_sorted(i, j, a)) {
 
                    // According to observation as given
                    // in approach
                    count += a.Length - j;
                    break;
                }
            }
        }
        return count;
    }
 
    // Driver code
    public static void Main(string[] args)
    {
        int[] A = { 5, 3, 1, 5, 2 };
 
        Console.WriteLine(countp(A));
    }
}
 
// This code is contributed by ukasp.

Javascript

<script>
 
// JavaScript program to implement the above approach
 
// function to chk array is sorted or not
function chk_sorted(l, r, a){
 
    // taking range element separately
    // to be removed
    l = a.slice(l, r + 1)
 
 
    let chk = []
    for (let i of a){
        // checking is all range element
        // occurrence is removed
        if(!l.includes(i)){
            chk.push(i)
        }
    }
 
 
    let chk1 = [...chk]
 
    chk1.sort()
     
    // if array is sorted return true
 
    if(chk1.every((val, index) => val == chk[index]))
        return true
    else
        return false
}
 
 
// function to count all good ranges
function countp(a){
 
    // initial count 0
    let count = 0
 
    // nested loop implementation
    for (let i  = 0; i < a.length; i++){
        for(let j = i + 1; j < a.length; j++){
 
            // checking if range is good
            if(chk_sorted(i, j, a)){
 
                // according to observation as given
                // in approach
                count += a.length - j
                break
            }
        }
    }
    return count
}
 
 
// Driver code
let N = 5
let A = [5, 3, 1, 5, 2]
document.write(countp(A))
 
</script>
Producción

7

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

Publicación traducida automáticamente

Artículo escrito por ShubhamSingh53 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 *