给定n个整数，发现最大数不是完美平方。如果没有完全正方形的数字，请打印-1。 例如：
null
Input : arr[] = {16, 20, 25, 2, 3, 10| Output : 20 Explanation: 20 is the largest number that is not a perfect square Input : arr[] = {36, 64, 10, 16, 29, 25| Output : 29
A. 正常溶液 就是对元素进行排序，对n个数字进行排序，然后使用sqrt（）函数从后面开始检查非完美的平方数。从末尾开始的第一个数字不是一个完美的平方数，这就是我们的答案。排序的复杂性很高 O（n日志n） sqrt（）函数的值是logn，所以在最坏的情况下，复杂度是 O（n logn logn）。 这个 有效解决方案 就是使用O（n）中的遍历对所有元素进行迭代，每次都与最大元素进行比较，并存储所有非完美平方的最大值。存储在最大值中的数字将是我们的答案。 以下是上述方法的说明：
CPP
// CPP program to find the largest non perfect // square number among n numbers #include <bits/stdc++.h> using namespace std; bool check( int n) { // takes the sqrt of the number int d = sqrt (n); // checks if it is a perfect square number if (d * d == n) return true ; return false ; } // function to find the largest non perfect square number int largestNonPerfectSquareNumber( int a[], int n) { // stores the maximum of all non perfect square numbers int maxi = -1; // traverse for all elements in the array for ( int i = 0; i < n; i++) { // store the maximum if not a perfect square if (!check(a[i])) maxi = max(a[i], maxi); } return maxi; } // driver code to check the above functions int main() { int a[] = { 16, 20, 25, 2, 3, 10 }; int n = sizeof (a) / sizeof (a[0]); // function call cout << largestNonPerfectSquareNumber(a, n); return 0; } |
JAVA
// Java program to find the // largest non perfect // square number among n numbers import java.io.*; class GfG{ static Boolean check( int n) { // takes the sqrt of the number int d = ( int )Math.sqrt(n); // checks if it is a perfect square number if (d * d == n) return true ; return false ; } // function to find the largest // non perfect square number static int largestNonPerfectSquareNumber( int a[], int n) { // stores the maximum of all // non perfect square numbers int maxi = - 1 ; // traverse for all elements in the array for ( int i = 0 ; i < n; i++) { // store the maximum if // not a perfect square if (!check(a[i])) maxi = Math.max(a[i], maxi); } return maxi; } public static void main (String[] args) { int a[] = { 16 , 20 , 25 , 2 , 3 , 10 }; int n = a.length; // function call System.out.println(largestNonPerfectSquareNumber(a, n)); } } // This code is contributed by Gitanjali. |
Python3
# python program to find # the largest non perfect # square number among n numbers import math def check( n): # takes the sqrt of the number d = int (math.sqrt(n)) # checks if it is a # perfect square number if (d * d = = n): return True return False # function to find the largest # non perfect square number def largestNonPerfectSquareNumber(a, n): # stores the maximum of all # non perfect square numbers maxi = - 1 # traverse for all elements # in the array for i in range ( 0 ,n): # store the maximum if # not a perfect square if (check(a[i]) = = False ): maxi = max (a[i], maxi) return maxi # driver code a = [ 16 , 20 , 25 , 2 , 3 , 10 ] n = len (a) # function call print (largestNonPerfectSquareNumber(a, n)) # This code is contributed by Gitanjali. |
C#
// C# program to find the largest non perfect // square number among n numbers using System; class GfG { static bool check( int n) { // takes the sqrt of the number int d = ( int )Math.Sqrt(n); // checks if it is a perfect // square number if (d * d == n) return true ; return false ; } // function to find the largest // non perfect square number static int largestNonPerfectSquareNumber( int []a, int n) { // stores the maximum of all // non perfect square numbers int maxi = -1; // traverse for all elements in // the array for ( int i = 0; i < n; i++) { // store the maximum if // not a perfect square if (!check(a[i])) maxi = Math.Max(a[i], maxi); } return maxi; } // driver code to check the above functions public static void Main () { int []a = { 16, 20, 25, 2, 3, 10 }; int n = a.Length; // function call Console.WriteLine( largestNonPerfectSquareNumber(a, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program to find // the largest non perfect // square number among n // numbers function check( $n ) { // takes the sqrt // of the number $d = sqrt( $n ); // checks if it is a // perfect square number if ( $d * $d == $n ) return true; return false; } // function to find the largest // non perfect square number function largestNonPerfectSquareNumber( $a , $n ) { // stores the maximum of // all non perfect square // numbers $maxi = -1; // traverse for all // elements in the array for ( $i = 0; $i < $n ; $i ++) { // store the maximum if // not a perfect square if (!check( $a [ $i ])) $maxi = max( $a [ $i ], $maxi ); } return $maxi ; } // Driver Code $a = array (16, 20, 25, 2, 3, 10); $n = count ( $a ); // function call echo largestNonPerfectSquareNumber( $a , $n ); // This code is contributed by anuj_67. ?> |
Javascript
<script> // JavaScript program to find the // largest non perfect // square number among n numbers function check(n) { // takes the sqrt of the number let d = Math.sqrt(n); // checks if it is a perfect square number if (d * d == n) return true ; return false ; } // function to find the largest // non perfect square number function largestNonPerfectSquareNumber(a, n) { // stores the maximum of all // non perfect square numbers let maxi = -1; // traverse for all elements in the array for (let i = 0; i < n; i++) { // store the maximum if // not a perfect square if (!check(a[i])) maxi = Math.max(a[i], maxi); } return maxi; } // Driver Code let a = [ 16, 20, 25, 2, 3, 10 ]; let n = a.length; // function call document.write(largestNonPerfectSquareNumber(a, n)); </script> |
输出：
20
时间复杂度可以被认为是O（n），因为对于固定大小（32位或64位）的整数，sqrt（）函数可以在O（1）时间内实现[参考 维基 详细信息]
?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
