给定一系列 积极乐观的 整数，找到最大可能值K，这样数组至少有K个大于或等于K的元素。数组未排序，可能包含重复值。 例如：
null
Input: [2, 3, 4, 5, 6, 7]Output: 4Explanation : 4 elements [4, 5, 6, 7] are greater than equal to 4Input: [1, 2, 3, 4]Output: 2Explanation : 3 elements [2, 3, 4] are greater than equal to 2Input: [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: 5Explanation : All 5 elements are greater than equal to 5
预期时间复杂度：O（n）
方法1[简单：O（n） 2. )[时间] 让输入数组的大小为n。让我们考虑以下重要的观察结果。
- 结果的最大可能值可以是n。当所有元素都大于或等于n时，我们得到最大可能值。例如，如果输入数组是{10,20,30}，n是3。结果的值不能大于3。
- 最小可能值为1。获取此输出时的一个示例情况是，当所有元素都为1时。
所以我们可以运行一个从n到1的循环，为每个值计算更多的元素。
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> |
输出：
3
方法2[有效：O（n）时间和O（n）额外空间] 1） 其思想是构造大小为n+1的辅助数组，并使用该数组查找输入数组中较大元素的计数。让辅助数组为freq[]。我们将该数组的所有元素初始化为0。 2） 我们处理所有的输入元素。 a） 如果一个元素arr[i]小于n，那么我们增加它的频率，也就是说，我们做freq[arr[i]++。 b） 否则我们增加频率。 3） 在第二步之后，我们有两件事。 a） 频率[0..n-1]中存储的小于n的元素的元素频率。 b） 存储在freq[n]中大于n的元素计数。 最后，我们向后处理freq[]数组，通过保持到目前为止处理的值之和来找到输出。 下面是上述想法的实现。
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*/ |
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> |
输出：
3
本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
