首页 > 其他 > 详细

Leetcode 69. Sqrt(x)

时间:2016-07-02 11:46:58      阅读:104      评论:0      收藏:0      [点我收藏+]

69. Sqrt(x)

Total Accepted: 99997 Total Submissions: 388728 Difficulty: Medium

 

Implement int sqrt(int x).

Compute and return the square root of x.

 

思路:可以直接用sqrt函数。但实际上这题考察的是二分查找。

代码:
最简单的方法:

1 class Solution {
2 public:
3     int mySqrt(int x) {//1579205274
4         int half=(int)sqrt(x);
5         return half;
6     }
7 };

 

二分查找:

 1 class Solution {
 2 public:
 3     int mySqrt(int x) {//1579205274
 4         if(x<=1){
 5             return x;
 6         }
 7         int left=1,right=x,mid;//左闭右开
 8         while(left<right){
 9             mid=left+(right-left)/2;//直接使用(high + low) / 2 可能导致溢出
10             if(x/mid>=mid){
11                 left=mid+1;
12             }
13             else{
14                 right=mid;
15             }
16         }
17         return left-1;
18     }
19 };

 

Leetcode 69. Sqrt(x)

原文:http://www.cnblogs.com/Deribs4/p/5634955.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!