IT博客汇 | [原]LeetCode-- Implement int sqrt(int x)

[原]LeetCode-- Implement int sqrt(int x)

csharp25发表于 2015-12-02 10:17:15

题目描述：

Implement int sqrt(int x).

Compute and return the square root of x.

求一个整数的完全平方数，但返回的是Int。

从n/2开始递减，找到 i*i == n，注意int溢出的处理（从Sqrt(int.MaxValue)开始递减)

实现代码：

public class Solution {
    public int MySqrt(int x) {
    if(x < 2){
	    return x;
	}
	if(x > int.MaxValue){
		x = int.MaxValue;
	}
	
	var half = 46340; // Sqrt(int.MaxValue)
	
	for(var i = half; i >= 1; i--){
		if(i * i == x){
			return i;
		}
		if(i * i < x){
			return i;
		}
	}
	
	return -1;
    }
}