valid-perfect-square

Valid Perfect Square – LeetCode 367

Problem

Description

Given a positive integer num, write a function which returns True if num is a perfect square else False.

Example

Input: 16
Returns: True

Input: 14
Returns: False

Answer

Original

Code

class Solution {
public:
    bool isPerfectSquare(int num) {
        long l = 0, r = num;
        while(l <= r){
            long mid = (l + r) / 2;
            long tmp = mid * mid;
            if(tmp < num)
                l = mid + 1;
            else if(tmp > num)
                r = mid - 1;
            else 
                return true;
        }
        return false;
    }
};

思路

不允许使用sqrt，那么就直接使用二分法进行查找，一旦找到了匹配值就返回true，否则返回false。时间复杂度$O(log{n})$，空间复杂度$O(1)$。
耗时$2$ ms，排名$70.68\%$

Better

思路

还没看到更好的思路。