Dada una array arr[] de tamaño N y cada elemento en la array arr[] está en el rango [1, N] y la array puede contener duplicados. La tarea es encontrar el número máximo de valores únicos que se pueden obtener de modo que el valor en cualquier índice i pueda ser:
- Aumentado en 1.
- Disminuido en 1.
- Dejado como está.
Nota: La operación se puede realizar solo una vez con cada índice y debe realizarse para todos los índices en la array arr[].
Ejemplos:
Entrada: arr[] = {1, 2, 4, 4}
Salida: 4
Explicación:
Una forma es realizar las siguientes operaciones para el índice:
1: Deje el valor en el primer índice (1) como está.
2: Deje el valor en el segundo índice (2) como está.
3: Deje el valor en el tercer índice (4) como está.
4: Incremente el valor en el cuarto índice (4) en 1.
Luego, la array se convierte en {1, 2, 4, 5} y hay 4 valores únicos.
Entrada: arr[]={3, 3, 3, 3}
Salida: 3
Explicación:
Una forma es realizar las siguientes operaciones para el índice:
1: Deje el valor en el primer índice (3) como está.
2: Disminuya el valor en el segundo índice (3) en 1.
3: Deje el valor en el tercer índice (3) como está.
4: Incremente el valor en el cuarto índice (3) en 1.
Luego, la array se convierte en {3, 2, 3, 4} y hay 3 valores únicos.
Acercarse:
- Para algún elemento arbitrario X presente en la array en el índice i , decidimos qué operación realizar en él teniendo en cuenta lo siguiente:
- Disminuimos el valor X en 1 si el valor ( X – 1 ) no está presente en la array y hay una o más X presentes en la array en diferentes índices.
- No cambiamos el valor X si el valor X está presente solo una vez en la array.
- Incrementamos el valor X en 1 si el valor ( X + 1 ) no está presente en la array y hay una o más X presentes en la array en diferentes índices .
- Al tomar las decisiones anteriores para cada elemento, podemos estar seguros de que el recuento final de elementos únicos que obtenemos es el máximo.
- Sin embargo, para realizar los pasos anteriores para cada índice y contar las ocurrencias del elemento X y actualizar continuamente la array arr[], el tiempo necesario sería cuadrático, lo que no es factible para arrays de gran tamaño.
- Una alternativa para reducir la complejidad del tiempo es ordenar inicialmente la array . Al ordenar, todos los elementos de la array se agrupan y todos los valores repetidos se juntan.
- Después de ordenar la array, dado que el rango de los números ya está dado y es fijo, se puede usar un mapa hash donde las claves del hash son los números en el rango [1, N] y el valor de cada clave es booleano que se utiliza para determinar si la clave está presente en la array o no.
- En este problema, dado que los índices en sí son las claves del hash, se usa una array freq[] de tamaño ( N + 2 ) para implementar el hash.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find the maximum number of
// unique values in the array
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number of
// unique values in the vector
int uniqueNumbers(vector<int> arr, int n)
{
// Sorting the given vector
sort(arr.begin(),arr.end());
// This array will store the frequency
// of each number in the array
// after performing the given operation
// initialise the array with 0
vector<int> freq(n+2,0) ;
// Loop to apply operation on
// each element of the array
for (int x = 0; x < n; x++) {
// Incrementing the value at index x
// if the value arr[x] - 1 is
// not present in the array
if (freq[arr[x] - 1] == 0) {
freq[arr[x] - 1]++;
}
// If arr[x] itself is not present, then it
// is left as it is
else if (freq[arr[x]] == 0) {
freq[arr[x]]++;
}
// If both arr[x] - 1 and arr[x] are present
// then the value is incremented by 1
else {
freq[arr[x] + 1]++;
}
}
// Variable to store the number of unique values
int unique = 0;
// Finding the unique values
for (int x = 0; x <= n + 1; x++) {
if (freq[x]) {
unique++;
}
}
// Returning the number of unique values
return unique;
}
// Driver Code
int main()
{
vector<int> arr= { 3, 3, 3, 3 };
// Size of the vector
int n = arr.size();
int ans = uniqueNumbers(arr, n);
cout << ans;
return 0;
}
C
// C program to find the maximum number of
// unique values in the array
#include <stdio.h>
#include <stdlib.h>
// comparison function for qsort
int cmpfunc (const void * a, const void * b) {
return ( *(int*)a - *(int*)b );}
// Function to find the maximum number of
// unique values in the array
int uniqueNumbers(int* arr, int n)
{
// Sorting the given array
qsort(arr, n, sizeof(int), cmpfunc);
// This array will store the frequency
// of each number in the array
// after performing the given operation
int freq[n+2];
// initialise the array with 0
for(int i = 0 ; i < n + 2 ; i++)
freq[i] = 0;
// Loop to apply operation on
// each element of the array
for (int x = 0; x < n; x++) {
// Incrementing the value at index x
// if the value arr[x] - 1 is
// not present in the array
if (freq[arr[x] - 1] == 0) {
freq[arr[x] - 1]++;
}
// If arr[x] itself is not present, then it
// is left as it is
else if (freq[arr[x]] == 0) {
freq[arr[x]]++;
}
// If both arr[x] - 1 and arr[x] are present
// then the value is incremented by 1
else {
freq[arr[x] + 1]++;
}
}
// Variable to store the number of unique values
int unique = 0;
// Finding the unique values
for (int x = 0; x <= n + 1; x++) {
if (freq[x]) {
unique++;
}
}
// Returning the number of unique values
return unique;
}
// Driver Code
int main()
{
int arr[] = { 3, 3, 3, 3 };
// Size of the array
int n = sizeof(arr)/sizeof(arr[0]);
int ans = uniqueNumbers(arr, n);
printf("%d", ans);
return 0;
}
// This code is contributed by phalashi.
Java
// Java program to find the maximum number of
// unique values in the array
import java.util.*;
class GFG {
// Function to find the maximum number of
// unique values in the array
static int uniqueNumbers(int arr[], int n)
{
// Sorting the given array
Arrays.sort(arr);
// This array will store the frequency
// of each number in the array
// after performing the given operation
int freq[] = new int[n + 2];
// Initialising the array with all zeroes
for(int i = 0; i < n + 2; i++)
freq[i] = 0;
// Loop to apply operation on
// each element of the array
for (int x = 0; x < n; x++) {
// Incrementing the value at index x
// if the value arr[x] - 1 is
// not present in the array
if (freq[arr[x] - 1] == 0) {
freq[arr[x] - 1]++;
}
// If arr[x] itself is not present, then it
// is left as it is
else if (freq[arr[x]] == 0) {
freq[arr[x]]++;
}
// If both arr[x] - 1 and arr[x] are present
// then the value is incremented by 1
else {
freq[arr[x] + 1]++;
}
}
// Variable to store the number of unique values
int unique = 0;
// Finding the unique values
for (int x = 0; x <= n + 1; x++) {
if (freq[x] != 0) {
unique++;
}
}
// Returning the number of unique values
return unique;
}
// Driver Code
public static void main (String[] args)
{
int []arr = { 3, 3, 3, 3 };
// Size of the array
int n = 4;
int ans = uniqueNumbers(arr, n);
System.out.println(ans);
}
}
// This code is contributed by Yash_R
Python3
# Python program to find the maximum number of # unique values in the array # Function to find the maximum number of # unique values in the array def uniqueNumbers(arr, n): # Sorting the given array arr.sort() # This array will store the frequency # of each number in the array # after performing the given operation freq =[0]*(n + 2) # Loop to apply the operation on # each element of the array for val in arr: # Incrementing the value at index x # if the value arr[x] - 1 is # not present in the array if(freq[val-1]== 0): freq[val-1]+= 1 # If arr[x] itself is not present, then it # is left as it is elif(freq[val]== 0): freq[val]+= 1 # If both arr[x] - 1 and arr[x] are present # then the value is incremented by 1 else: freq[val + 1]+= 1 # Variable to store the # number of unique values unique = 0 # Finding the number of unique values for val in freq: if(val>0): unique+= 1 return unique # Driver code if __name__ == "__main__": arr =[3, 3, 3, 3] n = 4 print(uniqueNumbers(arr, n))
C#
// C# program to find the maximum number of
// unique values in the array
using System;
class GFG {
// Function to find the maximum number of
// unique values in the array
static int uniqueNumbers(int []arr, int n)
{
// Sorting the given array
Array.Sort(arr);
// This array will store the frequency
// of each number in the array
// after performing the given operation
int []freq = new int[n + 2];
// Initialising the array with all zeroes
for(int i = 0; i < n + 2; i++)
freq[i] = 0;
// Loop to apply operation on
// each element of the array
for (int x = 0; x < n; x++) {
// Incrementing the value at index x
// if the value arr[x] - 1 is
// not present in the array
if (freq[arr[x] - 1] == 0) {
freq[arr[x] - 1]++;
}
// If arr[x] itself is not present, then it
// is left as it is
else if (freq[arr[x]] == 0) {
freq[arr[x]]++;
}
// If both arr[x] - 1 and arr[x] are present
// then the value is incremented by 1
else {
freq[arr[x] + 1]++;
}
}
// Variable to store the number of unique values
int unique = 0;
// Finding the unique values
for (int x = 0; x <= n + 1; x++) {
if (freq[x] != 0) {
unique++;
}
}
// Returning the number of unique values
return unique;
}
// Driver Code
public static void Main (string[] args)
{
int []arr = { 3, 3, 3, 3 };
// Size of the array
int n = 4;
int ans = uniqueNumbers(arr, n);
Console.WriteLine(ans);
}
}
// This code is contributed by Yash_R
Javascript
<script>
// javascript program to find the maximum number of
// unique values in the array
// Function to find the maximum number of
// unique values in the array
function uniqueNumbers(arr , n) {
// Sorting the given array
arr.sort((a,b)=>a-b);
// This array will store the frequency
// of each number in the array
// after performing the given operation
var freq = Array(n + 2).fill(0);
// Initialising the array with all zeroes
for (i = 0; i < n + 2; i++)
freq[i] = 0;
// Loop to apply operation on
// each element of the array
for (x = 0; x < n; x++) {
// Incrementing the value at index x
// if the value arr[x] - 1 is
// not present in the array
if (freq[arr[x] - 1] == 0) {
freq[arr[x] - 1]++;
}
// If arr[x] itself is not present, then it
// is left as it is
else if (freq[arr[x]] == 0) {
freq[arr[x]]++;
}
// If both arr[x] - 1 and arr[x] are present
// then the value is incremented by 1
else {
freq[arr[x] + 1]++;
}
}
// Variable to store the number of unique values
var unique = 0;
// Finding the unique values
for (x = 0; x <= n + 1; x++) {
if (freq[x] != 0) {
unique++;
}
}
// Returning the number of unique values
return unique;
}
// Driver Code
var arr = [ 3, 3, 3, 3 ];
// Size of the array
var n = 4;
var ans = uniqueNumbers(arr, n);
document.write(ans);
// This code contributed by Rajput-Ji
</script>
Producción:
3
Análisis de la Complejidad del Tiempo:
- El tiempo necesario para ordenar la array dada es O(N * log(N)) donde N es el tamaño de la array.
- El tiempo necesario para ejecutar un ciclo sobre la array ordenada para realizar las operaciones es O(N) .
- El tiempo necesario para ejecutar un ciclo sobre el hash para contar los valores únicos es O(N) .
- Por lo tanto, la complejidad temporal general es O(N * log(N)) + O(N) + O(N) . Dado que N * log(N) es mayor, la complejidad de tiempo final del enfoque anterior es O(N * log(N)) .
Espacio Auxiliar: O(N)
- El espacio adicional que ocupa la array de frecuencias es O(N). Por lo tanto el espacio auxiliar es O(N).
Publicación traducida automáticamente
Artículo escrito por shobhitgupta907 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA