Implement int sqrt(int x).
Compute and return the square root of x.
二分法,但是用除法来检测,避免溢出。
public class Solution { //Time: O(logn) Space: O(1) public int sqrt(int x) { if (x == 0 || x == 1) { return x; } int left = 1; int right = x; while (left + 1 < right) { int mid = left + (right - left) / 2; if (x / mid == mid) { return mid; } else if (x / mid > mid) { left = mid; } else { right = mid; } } if (x / right > right) { return right; } else { return left; } } }
No comments:
Post a Comment