LeetCode 69. Sqrt(x) （平方根）

Implement int sqrt(int x).

Compute and return the square root of x.

x is guaranteed to be a non-negative integer.

Example 1:

Input: 4

Output: 2

Example 2:

Input: 8

Output: 2

Explanation: The square root of 8 is 2.82842..., and since we want to return an integer, the decimal part will be truncated.

题目标签：Math

　　题目给了我们一个x，让我们找到平方根。

　　可以利用binary search 来做，首先找到一个范围，不需要是从0 到 x。因为 sqrt(x) 一定是小于等于 x / 2 + 1的。

　　所以起始范围为 0 到 x / 2 + 1;

　　还要注意 sq = mid * mid。这里要检查 overflow。

Java Solution:

Runtime beats 53.10%

完成日期：06/12/2017

关键词：Binary Search

关键点：检查overflow

 class Solution

 {

     public int mySqrt(int x)

     {

         int left = 0;

         int right = x / 2 + 1;

         while(left <= right)

         {

             int mid = left + (right - left)/2;

             int sq = mid * mid;

             if(mid != 0 && sq / mid != mid) // check overflow

             {

                 right = mid - 1; // meaning mid is too big, go to left part

                 continue;

             }

             if(sq == x)

                 return mid;

             else if(sq < x)

                 left = mid + 1;

             else

                 right = mid - 1;

         }

         return right;

     }

 }

参考资料：N/A

LeetCode 题目列表 - LeetCode Questions List

题目来源：https://leetcode.com/

巴特西

LeetCode 69. Sqrt(x) （平方根）

最新文章

热门文章