leetcode: Sqrt(x)

问题描述：

Implement int sqrt(int x).

Compute and return the square root of x.

 

原问题链接：https://leetcode.com/problems/sqrtx/

 

问题分析

　这个问题的解决办法有若干种，主要的目的是通过给定的范围去尝试凑一个和给定目标值最接近的结果。我们针对几种常见的解法做讨论。

 

二分法

　　我们知道，求一个整数的平方根，而且还要求这个值取整数的话，我们可以参照二分查找的思路。首先取给定范围的最大和最小值，针对x来说，它的平方根所能取的最小值是0，而它的最大值肯定会小于x / 2 + 1。所以我们以这两个值作为判断查找的上下限。每次取它们的中间值mid,　直到mid * mid == x。

　　详细实现如下：

 

public class Solution {
    public int mySqrt(int x) {
        long i = 0;
        long j = x / 2 + 1;
        while (i <= j) {
            long mid = (i + j) / 2;
            if (mid * mid == x)
                return (int)mid;
            if (mid * mid < x)
                i = mid + 1;
            else
                j = mid - 1;
        }
        return (int)j;
    }
}

 　这种方法的实现效率比较高，在时间复杂度上达到了O(lgN)。

 

逐位尝试法

　　如果我们利用一些位运算的手法，可以发现另外一种思路。对于一个给定的32位整数来说，它的平方根值可能最多只能到16位，因为两个16位的值相乘就可以达到32位了。我们可以取一个比特位，它最开始是最高的第16位上为1。这个值和我们给定的一个尝试判断的值进行或运算。这样根据得到的值求平方，判断它是否大于我们给定的值x，如果大于x的话，我们就将这个位置成0，否则就保持这个位的值为1。然后再考虑下一位。这样我们只要遍历16个位进行运算就可以了。相当于运行的时间复杂度是常量范围的。

　　详细的实现如下：

 

public class Solution {
    public int mySqrt(int x) {
        long ans = 0;
        long bit = 1l << 16;
        while(bit > 0) {
            ans |= bit;
            if (ans * ans > x) {
                ans ^= bit;
            }
            bit >>= 1;
        }
        return (int)ans;
    }
}

 

参考材料

http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html