69. Sqrt(x)

Question:

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since the decimal part is truncated, 2 is returned.

Thinking:

Method:
- 可能性就是在1 - x之间，通过二分法查找出准确值。

class Solution {
    public int mySqrt(int x) {
        if(x == 0 || x == 1) return x;
        else{
            int mid = 0, low = 1, high = x;
            while(true){
                mid = (low + high) / 2;
                if(mid > x / mid)
                    high = mid - 1;
                else{
                    if(mid + 1 > x /(mid + 1))
                        return mid;
                    else
                        low = mid + 1;
                }
            }
        }
    }
}

二刷

二刷的时候还是参考了一刷的答案，实际上没有想到用二分法来做这道题。而且有个很有趣的现象，如果使用乘法来判断大小则无法AC，如果我们使用除法则可以做到AC。

class Solution {
    public int mySqrt(int x) {
        if(x == 0 || x == 1) return x;
        int low = 1, high = x, mid = 0;
        while(true){
            mid = low + (high - low) / 2;
            if(mid > x / mid)
                high = mid - 1;
            else{
                if((mid + 1) > (x / (mid + 1)))
                    return mid;
                else
                    low = mid + 1;
            }
        }
    }
}

Third Time

Method 1: binary search

 class Solution {
 	public int mySqrt(int x) {
 		if(x == 0 || x == 1) return x;
 		int left = 1, right = x / 2;
 		while(left <= right){
 			int mid = left + (right - left) / 2;
 			if(mid > x / mid) right = mid - 1;
 			else left = mid + 1;
 		}
 		return right;
 	}
 }

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!