首页 > 代码库 > Leetcode: Sqrt(x)
Leetcode: Sqrt(x)
Implement int sqrt(int x).
难度：76，用二分查找。要求是知道结果的范围，取定左界和右界，然后每次砍掉不满足条件的一半，知道左界和右界相遇。算法的时间复杂度是O(logx)，空间复杂度是O(1)。
1 public class Solution { 2 public int sqrt(int x) { 3 if (x < 0) { 4 return -1; 5 } 6 if (x == 0) { 7 return 0; 8 } 9 int l = 1;10 int r = x/2 + 1;11 while (l <= r) {12 int m = (l + r)/2;13 if (m <= x/m && x/(m+1) < m+1) return m;14 else if (m > x/m) {15 r = m - 1;16 }17 else {18 l = m + 1;19 }20 }21 return -1;22 }23 }
Leetcode: Sqrt(x)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。