Leetcode skimming ---367

subject ： Given a Positive integer num , Write a function , If num It's a complete square , Then return to true , Otherwise return to false .

Input ：num = 16

Output ：true

Method 1 ： Built in library functions

class Solution {
public:
    bool isPerfectSquare(int num) {
        int x = (int) sqrt(num);
        return x * x == num;
    }
};

Method 2 ： violence

class Solution {
public:
    bool isPerfectSquare(int num) {
        long x = 1, square = 1;
        while (square <= num) {
            if (square == num) {
                return true;
            }
            ++x;
            square = x * x;
        }
        return false;
    }
};

Complexity analysis

Time complexity ：O()

Spatial complexity ：O(1)

  Method 3 ： Two points search

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

Complexity analysis

Time complexity ：O(logn)

Spatial complexity ：O(1)

Method four ： Newton's iteration

class Solution {
public:
    bool isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;
    }
};

Complexity analysis

Time complexity ：O(logn)

Spatial complexity ：O(1)