Thursday, December 31, 2015

[Leetcode] Sqrt(x)

Problem

Implement int sqrt(int x).
Compute and return the square root of x.

Analysis


  • 二分搜索 [0,x]
    • 若 mid*mid 等于x,或者 (mid*mid<x && (mid+1)*(mid+1)>x), 则返回mid
    • 否则若mid*mid < x,则搜索 [mid+1, right]
    • 否则若mid*mid > x, 则搜索 [left, mid-1]
  • 注意 mid*mid 可能会溢出,要用long类型
  • Time: O(log n)
  • Space: O(1)

Code



Reference
[1] https://leetcode.com/problems/sqrtx/

No comments:

Post a Comment