My python solution, cost 77ms


  • 3
    W

    The main thought of my algorithm is binary search. Cost 77ms.

    class Solution:
        # @param x, an integer
        # @return an integer
        def sqrt(self, x):
            if x == 0:
                return 0
            low = 1
            high = x
            mark = 1
            while low != high - 1:
                mid = (high + low) / 2
                if mid * mid > x:
                    high = mid
                elif mid * mid < x:
                    mark = mid
                    low = mid
                else:
                    return mid
            return mark
    

    And I changed yuyibestman and tyuan73's java codes which using math method into python and improved a little bit. Cost 79ms.

    class Solution:
        # @param x, an integer
        # @return an integer
        def sqrt(self, x):
            ans = 0
            bit = 1l << 15
            while bit > 0:
                ans |= bit
                if ans * ans > x:
                    ans ^= bit
                bit >>= 1
            return int(ans)
    

    Wish these codes can help you.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.