Sqrt(x), Leetcode 解题笔记

Implement int sqrt(int x).

Compute and return the square root of x.

求开根号,只能用root*root = x来判断,但是root不能从1开始每次加1的试,如果x非常大那么肯定超时。怎么缩短时间呢,肯定要想到二分法:

public class Solution {
    public int sqrt(int x) {
        long low = 0;
        long high = x;
        while(high >= low){
            long mid = (low + high)/2;
            if(mid*mid == x){
                return (int)mid;
            }
            if(mid*mid < x){
                low = mid+1;
            }
            if(mid*mid > x){
                high = mid-1;
            }
        }
        return (int)high;
    }
}

注意用long来防止溢出。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s