Dada una array de N enteros , la tarea es calcular la longitud de la secuencia más larga de enteros consecutivos que se pueden formar a partir de la array. También se da que los 0 en la array se pueden convertir a cualquier valor.
Ejemplo:
Entrada: N = 7, A = {0, 6, 5, 10, 3, 0, 11}
Salida: 5
Explicación: La máxima secuencia consecutiva formada puede ser {3, 4, 5, 6, 7}. Como 4, 7 no están presentes en la array, podemos cambiar 2 ceros por 4 y 7.Entrada: N = 6, A = {0, 0, 1, 2, 6, 0}
Salida: 6
Explicación: La máxima secuencia consecutiva formada puede ser {1, 2, 3, 4, 5, 6}
Enfoque: el problema dado se puede resolver con la ayuda de la búsqueda binaria y la array de suma de prefijos :
- Calcule el total de ceros en la array y guárdelos en un recuento variable que indica el total de cambios posibles que se pueden realizar
- Los valores repetidos y cero en la array dada se eliminan para que la array contenga solo valores únicos distintos de cero
- Cree una array auxiliar e inicialice el valor de esos índices en 1, cuyos valores están presentes en la array dada
- La array auxiliar se convierte en una array de suma de prefijos
- Itere la array de prefijos y en cada iteración realice una búsqueda binaria con el límite inferior como índice actual y el límite superior como último índice de la array
- Sea l el índice actual y r el índice posible más a la derecha . Para cada mid = (l + r) / 2 , verifique si este rango [ l , mid ] se puede lograr con los cambios totales permitidos
- Actualice l = mid +1 si la declaración anterior es verdadera; de lo contrario , r = mid – 1
- Calcular la longitud máxima para todos los valores iniciales
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to calculate maximum
// possible consecutive numbers
// with changes allowed
int maximumConsecutiveNumbers(int arr[], int N)
{
// Store all non-zero elements
// in a new vector and
// calculate total zero elements
vector<int> v;
// Variable to store the
// count of zero elements
int count = 0;
for (int i = 0; i < N; i++) {
if (arr[i] == 0) {
count++;
}
else {
v.push_back(arr[i]);
}
}
// Sort the array
sort(v.begin(), v.end());
// Remove all the duplicates
// from the array
(v).erase(unique(v.begin(),
v.end()),
(v).end());
// Variable to store the maximum
// value of the sequence
int MAXN = 1100000;
// Make the prefix array
vector<int> pref(MAXN + 1, 0);
for (int i = 0; i < v.size(); i++) {
pref[v[i]]++;
}
for (int i = 1; i <= MAXN; i++) {
pref[i] += pref[i - 1];
}
int mx = 0;
// Iterate for each element and
// use binary search
for (int i = 1; i <= MAXN; i++) {
int l = i, r = MAXN;
int local_max = 0;
while (l <= r) {
int mid = (l + r) / 2;
// Conversions equal to number
// of zeros, can be made upto mid
if (pref[mid] - pref[i - 1]
+ count
>= (mid - i + 1)) {
l = mid + 1;
local_max = max(local_max,
mid - i + 1);
}
else {
r = mid - 1;
}
}
mx = max(mx, local_max);
}
return mx;
}
// Driver Code
int main()
{
int N = 7;
int arr[] = { 0, 6, 5, 10, 3, 0, 11 };
cout << maximumConsecutiveNumbers(arr, N);
}
Python3
# Python 3 implementation for the above approach # Function to calculate maximum # possible consecutive numbers # with changes allowed def maximumConsecutiveNumbers(arr, N): # Store all non-zero elements # in a new vector and # calculate total zero elements v = [] # Variable to store the # count of zero elements count = 0 for i in range(N): if(arr[i] == 0): count += 1 else: v.append(arr[i]) # Sort the array v.sort() # Remove all the duplicates # from the array v = set(v) v = list(v) # Variable to store the maximum # value of the sequence MAXN = 110000 # Make the prefix array pref = [0 for i in range(MAXN+1)] for i in range(len(v)): pref[v[i]] += 1 for i in range(1,MAXN+1,1): pref[i] += pref[i - 1] mx = 0 # Iterate for each element and # use binary search for i in range(1,MAXN+1,1): l = i r = MAXN local_max = 0 while (l <= r): mid = (l + r) // 2 # Conversions equal to number # of zeros, can be made upto mid if (pref[mid] - pref[i - 1] + count >= (mid - i + 1)): l = mid + 1 local_max = max(local_max,mid - i + 1) else: r = mid - 1 mx = max(mx, local_max) return mx # Driver Code if __name__ == '__main__': N = 7 arr = [0, 6, 5, 10, 3, 0, 11] print(maximumConsecutiveNumbers(arr, N)) # This code is contributed by ipg2016107.
C#
// C# implementation for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
class GFG
{
// Function to calculate maximum
// possible consecutive numbers
// with changes allowed
static int maximumConsecutiveNumbers(int[] arr, int N)
{
// Store all non-zero elements
// in a new vector and
// calculate total zero elements
List<int> v = new List<int>();
// Variable to store the
// count of zero elements
int count = 0;
for (int i = 0; i < N; i++) {
if (arr[i] == 0) {
count++;
}
else {
v.Add(arr[i]);
}
}
// Sort the array
v.Sort();
// Remove all the duplicates
// from the array
List<int> distinct = v.Distinct().ToList();
// Variable to store the maximum
// value of the sequence
int MAXN = 1100000;
// Make the prefix array
List<int> pref = new List<int>(new int[MAXN + 1]);
for (int i = 0; i < distinct.Count; i++) {
pref[distinct[i]]++;
}
for (int i = 1; i <= MAXN; i++) {
pref[i] += pref[i - 1];
}
int mx = 0;
// Iterate for each element and
// use binary search
for (int i = 1; i <= MAXN; i++) {
int l = i, r = MAXN;
int local_max = 0;
while (l <= r) {
int mid = (l + r) / 2;
// Conversions equal to number
// of zeros, can be made upto mid
if (pref[mid] - pref[i - 1] + count
>= (mid - i + 1)) {
l = mid + 1;
local_max
= Math.Max(local_max, mid - i + 1);
}
else {
r = mid - 1;
}
}
mx = Math.Max(mx, local_max);
}
return mx;
}
// Driver Code
public static void Main()
{
int N = 7;
int[] arr = { 0, 6, 5, 10, 3, 0, 11 };
Console.Write(maximumConsecutiveNumbers(arr, N));
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript implementation for the above approach
// Function to calculate maximum
// possible consecutive numbers
// with changes allowed
const maximumConsecutiveNumbers = (arr, N) => {
// Store all non-zero elements
// in a new vector and
// calculate total zero elements
let v = [];
// Variable to store the
// count of zero elements
let count = 0;
for (let i = 0; i < N; i++) {
if (arr[i] == 0) {
count++;
}
else {
v.push(arr[i]);
}
}
// Sort the array
// Remove all the duplicates
// from the array
v = [...new Set(v)];
// Variable to store the maximum
// value of the sequence
let MAXN = 1100000;
// Make the prefix array
let pref = new Array(MAXN + 1).fill(0);
for (let i = 0; i < v.length; i++) {
pref[v[i]]++;
}
for (let i = 1; i <= MAXN; i++) {
pref[i] += pref[i - 1];
}
let mx = 0;
// Iterate for each element and
// use binary search
for (let i = 1; i <= MAXN; i++) {
let l = i, r = MAXN;
let local_max = 0;
while (l <= r) {
let mid = parseInt((l + r) / 2);
// Conversions equal to number
// of zeros, can be made upto mid
if (pref[mid] - pref[i - 1]
+ count
>= (mid - i + 1)) {
l = mid + 1;
local_max = Math.max(local_max,
mid - i + 1);
}
else {
r = mid - 1;
}
}
mx = Math.max(mx, local_max);
}
return mx;
}
// Driver Code
let N = 7;
let arr = [0, 6, 5, 10, 3, 0, 11];
document.write(maximumConsecutiveNumbers(arr, N))
// This code is contributed by rakeshsahni
</script>
Producción
5
Complejidad de tiempo: O(N*log(K)), donde K es el valor máximo en el arreglo
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA