Dada una array de enteros positivos , encuentre el valor máximo posible K tal que la array tenga al menos K elementos que sean mayores o iguales a K. La array no está ordenada y puede contener valores duplicados.
Ejemplos:
Input: [2, 3, 4, 5, 6, 7]
Output: 4
Explanation : 4 elements [4, 5, 6, 7]
are greater than equal to 4
Input: [1, 2, 3, 4]
Output: 2
Explanation : 3 elements [2, 3, 4] are
greater than equal to 2
Input: [4, 7, 2, 3, 8]
Output: 3
Explanation : 4 elements [4, 7, 3, 8]
are greater than equal to 3
Input: [6, 7, 9, 8, 10]
Output: 5
Explanation : All 5 elements are greater
than equal to 5
Complejidad de tiempo esperada : O(n)
Método 1 [Simple: O(n 2 ) tiempo] :
Deje que el tamaño de la array de entrada sea n. Consideremos las siguientes observaciones importantes.
- El máximo valor posible de resultado puede ser n. Obtenemos el máximo valor posible cuando todos los elementos son mayores o iguales que n. Por ejemplo, si la array de entrada es {10, 20, 30}, n es 3. El valor del resultado no puede ser mayor que 3.
- El valor mínimo posible sería 1. Un caso de ejemplo cuando se obtiene este resultado es cuando todos los elementos son 1.
Entonces podemos ejecutar un ciclo de n a 1 y contar elementos mayores para cada valor.
C++
// C++ program to find maximum possible value K
// such that array has at-least K elements that
// are greater than or equals to K.
#include <iostream>
using namespace std;
// Function to return maximum possible value K
// such that array has atleast K elements that
// are greater than or equals to K
int findMaximumNum(unsigned int arr[], int n)
{
// output can contain any number from n to 0
// where n is length of the array
// We start a loop from n as we need to find
// maximum possible value
for (int i = n; i >= 1; i--)
{
// count contains total number of elements
// in input array that are more than equal to i
int count = 0;
// traverse the input array and find count
for (int j=0; j<n; j++)
if (i <= arr[j])
count++;
if (count >= i)
return i;
}
return 1;
}
// Driver code
int main()
{
unsigned int arr[] = {1, 2, 3, 8, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaximumNum(arr, n);
return 0;
}
Java
// Java program to find maximum
// possible value K such that
// array has at-least K elements
// that are greater than or equals to K.
import java.io.*;
class GFG
{
// Function to return maximum
// possible value K such that
// array has atleast K elements
// that are greater than or equals to K
static int findMaximumNum(int arr[],
int n)
{
// output can contain any
// number from n to 0 where
// n is length of the array
// We start a loop from n
// as we need to find
// maximum possible value
for (int i = n; i >= 1; i--)
{
// count contains total
// number of elements
// in input array that
// are more than equal to i
int count = 0;
// traverse the input
// array and find count
for (int j = 0; j < n; j++)
if (i <= arr[j])
count++;
if (count >= i)
return i;
}
return 1;
}
// Driver code
public static void main (String[] args)
{
int arr[] = {1, 2, 3, 8, 10 };
int n = arr.length;
System.out.println(findMaximumNum(arr, n));
}
}
// This code is contributed by aj_36
Python3
# python 3 program to find maximum possible value K # such that array has at-least K elements that # are greater than or equals to K. # Function to return maximum possible value K # such that array has atleast K elements that # are greater than or equals to K def findMaximumNum(arr, n): # output can contain any number from n to 0 # where n is length of the array # We start a loop from n as we need to find # maximum possible value i = n while(i >= 1): # count contains total number of elements # in input array that are more than equal to i count = 0 # traverse the input array and find count for j in range(0,n,1): if (i <= arr[j]): count += 1 if (count >= i): return i i -= 1 return 1 # Driver code if __name__ == '__main__': arr = [1, 2, 3, 8, 10] n = len(arr) print(findMaximumNum(arr, n)) # This code is contributed by # Surendra_Gangwar
C#
// C# program to find maximum
// possible value K such that
// array has at-least K elements
// that are greater than or equals to K.
using System;
class GFG
{
// Function to return maximum
// possible value K such that
// array has atleast K elements
// that are greater than or equals to K
static int findMaximumNum(int []arr,
int n)
{
// output can contain any
// number from n to 0 where
// n is length of the array
// We start a loop from n
// as we need to find
// maximum possible value
for (int i = n; i >= 1; i--)
{
// count contains total
// number of elements
// in input array that
// are more than equal to i
int count = 0;
// traverse the input
// array and find count
for (int j = 0; j < n; j++)
if (i <= arr[j])
count++;
if (count >= i)
return i;
}
return 1;
}
// Driver code
static public void Main ()
{
int []arr = {1, 2, 3, 8, 10 };
int n = arr.Length;
Console.WriteLine(findMaximumNum(arr, n));
}
}
// This code is contributed by m_kit
PHP
<?php
// PHP program to find maximum
// possible value K such that
// array has at-least K elements
// that are greater than or
// equals to K.
// Function to return maximum
// possible value K such that
// array has atleast K elements
// that are greater than or
// equals to K
function findMaximumNum($arr, $n)
{
// output can contain any
// number from n to 0 where
// n is length of the array
// We start a loop from
// n as we need to find
// maximum possible value
for ($i = $n; $i >= 1; $i--)
{
// count contains total
// number of elements in
// input array that are
// more than equal to i
$count = 0;
// traverse the input
// array and find count
for ($j = 0; $j < $n; $j++)
if ($i <= $arr[$j])
$count++;
if ($count >= $i)
return $i;
}
return 1;
}
// Driver code
$arr = array (1, 2, 3, 8, 10);
$n = sizeof($arr);
echo findMaximumNum($arr, $n);
// This code is contributed by ajit
?>
Javascript
<script>
// Javascript program to find maximum
// possible value K such that
// array has at-least K elements
// that are greater than or equals to K.
// Function to return maximum
// possible value K such that
// array has atleast K elements
// that are greater than or equals to K
function findMaximumNum(arr, n)
{
// output can contain any
// number from n to 0 where
// n is length of the array
// We start a loop from n
// as we need to find
// maximum possible value
for (let i = n; i >= 1; i--)
{
// count contains total
// number of elements
// in input array that
// are more than equal to i
let count = 0;
// traverse the input
// array and find count
for (let j = 0; j < n; j++)
if (i <= arr[j])
count++;
if (count >= i)
return i;
}
return 1;
}
let arr = [1, 2, 3, 8, 10 ];
let n = arr.length;
document.write(findMaximumNum(arr, n));
</script>
Producción
3
Método 2 [Eficiente: O(n) tiempo y O(n) espacio extra]
- La idea es construir una array auxiliar de tamaño n + 1 y usar esa array para encontrar el recuento de elementos más grandes en la array de entrada. Deje que la array auxiliar sea freq[]. Inicializamos todos los elementos de esta array como 0.
- Procesamos todos los elementos de entrada.
- Si un elemento arr[i] es menor que n, entonces incrementamos su frecuencia, es decir, hacemos freq[arr[i]]++.
- De lo contrario incrementamos freq[n].
- Después del paso 2 tenemos dos cosas.
- Frecuencias de elementos para elementos menores que n almacenados en freq[0..n-1].
- Recuento de elementos mayores que n almacenados en freq[n].
Finalmente, procesamos la array freq[] hacia atrás para encontrar la salida manteniendo la suma de los valores procesados hasta el momento.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to find maximum possible value K such
// that array has atleast K elements that are greater
// than or equals to K.
#include <bits/stdc++.h>
using namespace std;
// Function to return maximum possible value K such
// that array has at-least K elements that are greater
// than or equals to K.
int findMaximumNum(unsigned int arr[], int n)
{
// construct auxiliary array of size n + 1 and
// initialize the array with 0
vector<int> freq(n+1, 0);
// store the frequency of elements of
// input array in the auxiliary array
for (int i = 0; i < n; i++)
{
// If element is smaller than n, update its
// frequency
if (arr[i] < n)
freq[arr[i]]++;
// Else increment count of elements greater
// than n.
else
freq[n]++;
}
// sum stores number of elements in input array
// that are greater than or equal to current
// index
int sum = 0;
// scan auxiliary array backwards
for (int i = n; i > 0; i--)
{
sum += freq[i];
// if sum is greater than current index,
// current index is the answer
if (sum >= i)
return i;
}
}
// Driver code
int main()
{
unsigned int arr[] = {1, 2, 3, 8, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
cout << findMaximumNum(arr, n);
return 0;
}
Java
// Java program to find maximum possible value K such
// that array has atleast K elements that are greater
// than or equals to K.
import java.util.Vector;
class GFG {
// Function to return maximum possible value K such
// that array has at-least K elements that are greater
// than or equals to K.
static int findMaximumNum(int arr[], int n) {
// construct auxiliary array of size n + 1 and
// initialize the array with 0
int[] freq=new int[n+1];
for (int i = 0; i < n + 1; i++) {
freq[i] = 0;
}
// store the frequency of elements of
// input array in the auxiliary array
for (int i = 0; i < n; i++) {
// If element is smaller than n, update its
// frequency
if (arr[i] < n) //
{
freq[arr[i]]++;
} // Else increment count of elements greater
// than n.
else {
freq[n]++;
}
}
// sum stores number of elements in input array
// that are greater than or equal to current
// index
int sum = 0;
// scan auxiliary array backwards
for (int i = n; i > 0; i--) {
sum += freq[i];
// if sum is greater than current index,
// current index is the answer
if (sum >= i) {
return i;
}
}
return 0;
}
// Driver code
public static void main(String[] args) {
int arr[] = {1, 2, 3, 8, 10};
int n = arr.length;
System.out.println(findMaximumNum(arr, n));
}
}
/*This Java code is contributed by koulick_sadhu*/
Python3
# Python program to find maximum possible value K such # that array has atleast K elements that are greater # than or equals to K. # Function to return maximum possible value K such # that array has at-least K elements that are greater # than or equals to K. def findMaximumNum(arr, n): # construct auxiliary array of size n + 1 and # initialize the array with 0 freq = [0 for i in range(n+1)] # store the frequency of elements of # input array in the auxiliary array for i in range(n): # If element is smaller than n, update its # frequency if (arr[i] < n): freq[arr[i]] += 1 # Else increment count of elements greater # than n. else: freq[n] += 1 # sum stores number of elements in input array # that are greater than or equal to current # index sum = 0 # scan auxiliary array backwards for i in range(n,0,-1): sum += freq[i] # if sum is greater than current index, # current index is the answer if (sum >= i): return i # Driver code arr = [1, 2, 3, 8, 10] n = len(arr) print(findMaximumNum(arr, n)) # This code is contributed by shinjanpatra
C#
// C# program to find maximum possible value K such
// that array has atleast K elements that are greater
// than or equals to K.
using System;
using System.Collections.Generic;
class GFG
{
// Function to return maximum possible value K such
// that array has at-least K elements that are greater
// than or equals to K.
static int findMaximumNum(int []arr, int n)
{
// construct auxiliary array of size n + 1 and
// initialize the array with 0
List<int> freq = new List<int>();
for (int i = 0; i < n + 1; i++)
{
freq.Insert(i, 0);
}
// store the frequency of elements of
// input array in the auxiliary array
for (int i = 0; i < n; i++)
{
// If element is smaller than n, update its
// frequency
if (arr[i] < n) //freq[arr[i]]++;
{
freq.Insert(arr[i], freq[arr[i]] + 1);
}
// Else increment count of elements greater
// than n.
else
{
freq.Insert(n, freq[n] + 1);
}
//freq[n]++;
}
// sum stores number of elements in input array
// that are greater than or equal to current
// index
int sum = 0;
// scan auxiliary array backwards
for (int i = n; i > 0; i--)
{
sum += freq[i];
// if sum is greater than current index,
// current index is the answer
if (sum >= i)
{
return i;
}
}
return 0;
}
// Driver code
public static void Main()
{
int []arr = {1, 2, 3, 8, 10};
int n = arr.Length;
Console.WriteLine(findMaximumNum(arr, n));
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript program to find maximum possible value K such
// that array has atleast K elements that are greater
// than or equals to K.
// Function to return maximum possible value K such
// that array has at-least K elements that are greater
// than or equals to K.
function findMaximumNum(arr, n)
{
// construct auxiliary array of size n + 1 and
// initialize the array with 0
let freq = new Array(n + 1).fill(0);
// store the frequency of elements of
// input array in the auxiliary array
for (let i = 0; i < n; i++) {
// If element is smaller than n, update its
// frequency
if (arr[i] < n)
freq[arr[i]]++;
// Else increment count of elements greater
// than n.
else
freq[n]++;
}
// sum stores number of elements in input array
// that are greater than or equal to current
// index
let sum = 0;
// scan auxiliary array backwards
for (let i = n; i > 0; i--) {
sum += freq[i];
// if sum is greater than current index,
// current index is the answer
if (sum >= i)
return i;
}
}
// Driver code
let arr = [1, 2, 3, 8, 10];
let n = arr.length;
document.write(findMaximumNum(arr, n));
// This code is contributed by gfgking.
</script>
Producción
3
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA