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:
- Inicialice la lista l para almacenar todos los elementos del subarreglo de l a r en el arreglo a[].
- Inicialice la array chk[] para almacenar los elementos de la array [] que no están presentes en el rango [l, r].
- Iterar sobre el rango [0, N] usando la variable i y realizar los siguientes pasos:
- Inicialice la lista chk1 para almacenar la array chk[].
- Ordene la lista chk1 y verifique si chk1 es igual a chk, luego devuelva verdadero , de lo contrario, falso.
- 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 .
- Iterar sobre el rango [i+1, N] usando la variable i y realizar los siguientes pasos:
- 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>
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