LeetCode Sqrt(x) 整数平方根 java

你的名字 2022-07-18 05:46 190阅读 0赞

http://oj.leetcode.com/problems/sqrtx/

求一个整数的平方根，如果该整数的平方根不是整数的话，返回平方根取整。

最简单办法，暴力搜索从1到N/2搜索但会TLE。

二分搜索，开始区间是1，终止区间是x。

AC代码：

**\[java\]**  [view plain][]   [copy][view plain]

[![在CODE上查看代码片][CODE]][CODE_CODE] [![派生到我的代码片][ico_fork.svg]][ico_fork.svg 1]

1.  **public** **class** Solution \{  
2.      **public** **int** sqrt(**int** x) \{  
3.          **if**(x<=1) \{  
4.              **return** x;  
5.          \}  
6.            
7.          **int** begin = 1;  
8.          **int** end   = x;  
9.          **int** middle = 0;  
10.         **while**(begin<=end) \{  
11.             middle = begin + (end - begin)/2;  
12.             //不要写成middle\*middle==x，会溢出  
13.             **if**(middle==x/middle) \{  
14.                 **return** middle;  
15.             \} **else** \{  
16.                 **if** (middle<x/middle) \{  
17.                     begin = middle + 1;  
18.                 \} **else** \{  
19.                     end = middle - 1;  
20.                 \}  
21.             \}  
22.               
23.         \}   
24.         //结束条件end一定<begin，所以返回end  
25.         **return** end;  
26.     \}  
27. \}

这道题还有一种变形是给你一个数x，判断是否是一个完全平方数。基本思路一样，二分搜索1到x/2，结束条件是begin的平方大于x。

[view plain]: http://blog.csdn.net/worldwindjp/article/details/18887327#
[CODE]: https://code.csdn.net/assets/CODE_ico.png
[CODE_CODE]: https://code.csdn.net/snippets/175603
[ico_fork.svg]: https://code.csdn.net/assets/ico_fork.svg
[ico_fork.svg 1]: https://code.csdn.net/snippets/175603/fork