Dado un arreglo de N números, encuentre la longitud del subarreglo más largo tal que K sea el segundo elemento más grande en la inserción.
Ejemplos:
Entrada: a[] = {9, 5, 5, 6, 8}, K = 7
Salida: 4
El subarreglo más largo es {9, 5, 5, 6}, en el que si se inserta K se convierte en {9, 5 , 5, 6, 7}, y
7 es el segundo elemento más grande en la array
Entrada: a[] = {9, 5, 5, 6, 8}, K = 10
Salida: 0
Dado que el número máximo en la array es menor que la de K, por lo tanto no es posible.
Entrada: a[] = {8, 5, 10, 10, 8}, K = 9
Salida: 5
9 es el segundo elemento más grande de toda la array
Un enfoque ingenuo es iterar para cada subarreglo posible y verificar si al insertar K, se convierte en el segundo elemento más grande o no. Ingenuamente, podemos almacenar la longitud del más largo de todos los subconjuntos posibles.
Complejidad de tiempo: O(N^2)
Espacio auxiliar: O(1)
Una solución eficiente es utilizar la técnica de dos punteros para resolver el problema anterior. A continuación se muestra el algoritmo para resolver el problema anterior.
- Inicialice dos punteros al frente y al final como 0, y una array visitada que marca si el índice ha sido visitado o no.
- Necesitamos un contenedor de conjuntos para que podamos colocar el segundo elemento más grande en cualquier rango en O (log N) y un mapa_desordenado para contar las frecuencias de los elementos en la array para decidir sobre la eliminación del conjunto.
- Inicialmente, verifique si existe o no un elemento que sea mayor que K o no, si no existe tal elemento, entonces el subarreglo no es posible.
- Inserte el elemento en a[end] en el conjunto y aumente su frecuencia en el mapa si el final del índice no ha sido visitado antes para evitar múltiples inserciones del mismo índice.
- Si el conjunto contiene solo un elemento, entonces la inserción de K es posible ya que solo tenemos elementos y como sabemos que existe al menos un elemento> k , entonces este subarreglo puede ser parte del subarreglo más largo, por lo tanto, lo contamos y avanzamos. el puntero final.
- Si el conjunto contiene más de un elemento, entonces el puntero s.end() apunta después del último elemento, por lo tanto, disminuirlo dos veces nos dará nuestro segundo elemento más grande en el frente del rango.
- Si el segundo elemento más grande es mayor que K, entonces este subarreglo no es posible, por lo tanto, debemos mover el primer puntero hacia adelante, pero antes de hacer esto, verifique si la frecuencia de a[frente] es 1 o no, si es así , luego elimínelo del conjunto, de lo contrario, simplemente disminuya la frecuencia en el mapa en 1, ya que el elemento existirá en cualquier índice> frente. Aumenta el puntero frontal en uno.
- Si el segundo elemento más grande no es mayor que K, simplemente aumente el puntero final en uno.
- Guarde la longitud más grande de extremo frontal y devuélvala.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the length of the longest
// subarray such that K is the second largest element
// on insertion
#include <bits/stdc++.h>
using namespace std;
// Function to find the length of longest subarray
int lengthOfLongestSubarray(int a[], int n, int k)
{
bool flag = 0;
// Check if any element exists which is
// greater than k or not
for (int i = 0; i < n; i++) {
if (a[i] > k)
flag = 1;
}
if (!flag) {
return 0;
}
// two pointers used
int front = 0;
int end = 0;
// find the maximum length
int maxi = 0;
// Map used to count frequencies
unordered_map<int, int> mpp;
// set used to find the second largest
// element in range front-end
set<int> s;
// initialize all index of array as 0
bool vis[n];
memset(vis, 0, sizeof vis);
// iterate till any of the pointer exceeds N
while (front < n && end < n) {
// length of longest subarray
maxi = max(maxi, end - front);
// if the current index has not been
// visited previously then insert it
// in the set and increase the frequency
// and mark it as visited.
if (!vis[end]) {
mpp[a[end]]++;
s.insert(a[end]);
vis[end] = 1;
}
// find the largest element in the set
auto it = s.end();
// if only one element is there in set,
// then insertion of K is possible which
// will include other elements
if (s.size() == 1) {
// increase the second pointer in order
// to include more elements in the subarray
end++;
continue;
}
// twice decrease the
// iterator as s.end() points to
// after the last element
it--;
// second largest element in set
it--;
int el = *it;
// if the second largest element is greater than the
// K, then it is not possible to insert element
// in range front-end, and thus decrease the
// frequency of a[front] and remove from set
// accordingly
if (el > k) {
if (mpp[a[front]] == 1) {
s.erase(a[front]);
mpp[a[front]]--;
}
else
mpp[a[front]]--;
// move ahead the first pointer
front++;
}
else {
// increase the second pointer
// if the second largest element is smaller
// than or equals to K
end++;
}
}
// at then end also check for last subarray length
maxi = max(maxi, end - front);
return maxi;
}
// Driver Code
int main()
{
int a[] = { 9, 5, 5, 6, 8 };
int n = sizeof(a) / sizeof(a[0]);
int k = 7;
cout << lengthOfLongestSubarray(a, n, k);
return 0;
}
Java
// Java program to find the length of the longest
// subarray such that K is the second largest element
// on insertion
import java.io.*;
import java.util.*;
class GFG
{
// Function to find the length of longest subarray
static int lengthOfLongestSubarray(int a[], int n, int k)
{
int flag = 0;
// Check if any element exists which is
// greater than k or not
for (int i = 0; i < n; i++)
{
if (a[i] > k)
flag = 1;
}
if (flag == 0)
{
return 0;
}
// two pointers used
int front = 0;
int end = 0;
// find the maximum length
int maxi = 0;
Map<Integer, Integer> mpp = new HashMap<Integer, Integer>();
Set<Integer> s = new HashSet<Integer>();
// initialize all index of array as 0
int[] vis = new int[n];
// iterate till any of the pointer exceeds N
while (front < n && end < n)
{
// length of longest subarray
maxi = Math.max(maxi, end - front);
// if the current index has not been
// visited previously then insert it
// in the set and increase the frequency
// and mark it as visited.
if (vis[end] == 0)
{
if(mpp.containsKey(a[end]))
{
mpp.put(a[end], mpp.get(a[end]) + 1);
}
else
{
mpp.put(a[end], 1);
}
s.add(a[end]);
vis[end] = 1;
}
int it = s.size();
List<Integer> S = new ArrayList<Integer>(s);
Collections.sort(S);
// if only one element is there in set,
// then insertion of K is possible which
// will include other elements
if (S.size() == 1)
{
// increase the second pointer in order
// to include more elements in the subarray
end++;
continue;
}
// twice decrease the
// iterator as s.end() points to
// after the last element
it--;
// second largest element in set
it--;
int el = S.get(it);
// if the second largest element is greater than the
// K, then it is not possible to insert element
// in range front-end, and thus decrease the
// frequency of a[front] and remove from set
// accordingly
if (el > k)
{
if(mpp.get(a[front]) == 1)
{
mpp.put(a[front], mpp.get(a[front]) - 1);
}
else
{
mpp.put(a[front], mpp.get(a[front]) - 1);
}
// move ahead the first pointer
front++;
}
else
{
// increase the second pointer
// if the second largest element is smaller
// than or equals to K
end++;
}
}
// at then end also check for last subarray length
maxi = Math.max(maxi, end - front);
return maxi;
}
// Driver Code
public static void main (String[] args)
{
int[] a = { 9, 5, 5, 6, 8 };
int n = a.length;
int k = 7;
System.out.println(lengthOfLongestSubarray(a, n, k));
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to find the length of # the longest subarray such that K is # the second largest element on insertion # Function to find the length of longest subarray def lengthOfLongestSubarray(a, n, k): flag = 0 # Check if any element exists which is # greater than k or not for i in range(n): if (a[i] > k): flag = 1 if (flag == 0): return 0 # two pointers used front = 0 end = 0 # find the maximum length maxi = 0 # Map used to count frequencies mpp = dict() # set used to find the second largest # element in range front-end s = dict() # initialize all index of array as 0 vis = [0] * n # iterate till any of the pointer exceeds N while (front < n and end < n): # length of longest subarray maxi = max(maxi, end - front) # if the current index has not been # visited previously then insert it # in the set and increase the frequency # and mark it as visited. if (vis[end] == 0): mpp[a[end]] = mpp.get(a[end], 0) + 1 s[a[end]] = s.get(a[end], 0) + 1 vis[end] = 1 # find the largest element in the set iit = sorted(list(s)) it = len(iit) # if only one element is there in set, # then insertion of K is possible which # will include other elements if (len(s) == 1): # increase the second pointer in order # to include more elements in the subarray end += 1 continue # twice decrease the # iterator as s.end() points to # after the last element it -= 1 # second largest element in set it -= 1 el = iit[it] # if the second largest element is greater than the # K, then it is not possible to insert element # in range front-end, and thus decrease the # frequency of a[front] and remove from set # accordingly if (el > k): if (mpp[a[front]] == 1): del s[a[front]] mpp[a[front]] -= 1 else: mpp[a[front]] -= 1 # move ahead the first pointer front += 1 else : # increase the second pointer # if the second largest element is # smaller than or equals to K end += 1 # at then end also check for # last subarray length maxi = max(maxi, end - front) return maxi # Driver Code a = [9, 5, 5, 6, 8] n = len(a) k = 7 print(lengthOfLongestSubarray(a, n, k)) # This code is contributed by Mohit Kumar
C#
// C# program to find the length of the longest
// subarray such that K is the second largest element
// on insertion
using System;
using System.Collections.Generic;
public class GFG
{
// Function to find the length of longest subarray
static int lengthOfLongestSubarray(int[] a, int n, int k)
{
int flag = 0;
// Check if any element exists which is
// greater than k or not
for (int i = 0; i < n; i++)
{
if (a[i] > k)
flag = 1;
}
if (flag == 0)
{
return 0;
}
// two pointers used
int front = 0;
int end = 0;
// find the maximum length
int maxi = 0;
Dictionary<int, int> mpp =new Dictionary<int, int>();
SortedSet<int> s = new SortedSet<int>();
// initialize all index of array as 0
int[] vis = new int[n];
// iterate till any of the pointer exceeds N
while (front < n && end < n)
{
// length of longest subarray
maxi = Math.Max(maxi, end - front);
// if the current index has not been
// visited previously then insert it
// in the set and increase the frequency
// and mark it as visited.
if (vis[end] == 0)
{
if(mpp.ContainsKey(a[end]))
{
mpp[a[end]]++;
}
else
{
mpp.Add(a[end],1);
}
s.Add(a[end]);
vis[end] = 1;
}
int it = s.Count;
List<int> S = new List<int>(s);
if(S.Count == 1)
{
// increase the second pointer in order
// to include more elements in the subarray
end++;
continue;
}
// twice decrease the
// iterator as s.end() points to
// after the last element
it--;
// second largest element in set
it--;
int el = S[it];
// if the second largest element is greater than the
// K, then it is not possible to insert element
// in range front-end, and thus decrease the
// frequency of a[front] and remove from set
// accordingly
if (el > k)
{
if(mpp[a[front]] == 1)
{
mpp[a[front]]--;
}
else
{
mpp[a[front]]--;
}
front++;
}
else
{
// increase the second pointer
// if the second largest element is smaller
// than or equals to K
end++;
}
}
// at then end also check for last subarray length
maxi = Math.Max(maxi, end - front);
return maxi;
}
// Driver code
static public void Main (){
int[] a = { 9, 5, 5, 6, 8 };
int n = a.Length;
int k = 7;
Console.WriteLine(lengthOfLongestSubarray(a, n, k));
}
}
// This code is contributed by rag2127
Javascript
<script>
// Javascript program to find the length of the longest
// subarray such that K is the second largest element
// on insertion
// Function to find the length of longest subarray
function lengthOfLongestSubarray(a,n,k)
{
let flag = 0;
// Check if any element exists which is
// greater than k or not
for (let i = 0; i < n; i++)
{
if (a[i] > k)
flag = 1;
}
if (flag == 0)
{
return 0;
}
// two pointers used
let front = 0;
let end = 0;
// find the maximum length
let maxi = 0;
let mpp = new Map();
let s = new Set();
// initialize all index of array as 0
let vis = new Array(n);
for(let i=0;i<n;i++)
{
vis[i]=0;
}
// iterate till any of the pointer exceeds N
while (front < n && end < n)
{
// length of longest subarray
maxi = Math.max(maxi, end - front);
// if the current index has not been
// visited previously then insert it
// in the set and increase the frequency
// and mark it as visited.
if (vis[end] == 0)
{
if(mpp.has(a[end]))
{
mpp.set(a[end], mpp.get(a[end]) + 1);
}
else
{
mpp.set(a[end], 1);
}
s.add(a[end]);
vis[end] = 1;
}
let it = s.size;
let S = Array.from(s);
S.sort(function(a,b){return a-b;});
// if only one element is there in set,
// then insertion of K is possible which
// will include other elements
if (S.length == 1)
{
// increase the second pointer in order
// to include more elements in the subarray
end++;
continue;
}
// twice decrease the
// iterator as s.end() points to
// after the last element
it--;
// second largest element in set
it--;
let el = S[it];
// if the second largest element is greater than the
// K, then it is not possible to insert element
// in range front-end, and thus decrease the
// frequency of a[front] and remove from set
// accordingly
if (el > k)
{
if(mpp.get(a[front]) == 1)
{
mpp.set(a[front], mpp.get(a[front]) - 1);
}
else
{
mpp.set(a[front], mpp.get(a[front]) - 1);
}
// move ahead the first pointer
front++;
}
else
{
// increase the second pointer
// if the second largest element is smaller
// than or equals to K
end++;
}
}
// at then end also check for last subarray length
maxi = Math.max(maxi, end - front);
return maxi;
}
// Driver Code
let a=[ 9, 5, 5, 6, 8 ];
let n = a.length;
let k = 7;
document.write(lengthOfLongestSubarray(a, n, k));
// This code is contributed by patel2127
</script>
Producción
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)