[LeetCode] 69. Sqrt(x)

轉自LeetCode

Implement int sqrt(int x).

Compute and return the square root of x.

<Solution>

這題有兩種解法，一種是二分法，一種是牛頓法 (資料1, 資料2)

這邊使用牛頓法來處理

x_i+1=x_i - (x_i² - n) / (2x_i) = x_i - x_i / 2 + n / (2x_i) = x_i / 2 + n / 2x_i = (x_i + n/x_i) / 2

code 如下
c++

	class Solution {
	public:
	int mySqrt(int x) {
	if(x == 0) {
	return 0;
	}
	double ans = 1.0, prv = 0;
	while(ans != prv) {
	prv = ans;
	ans = (ans + x / ans) / 2;
	}
	return static_cast<int>(ans);
	}
	};

view raw sqrt.cpp hosted with ❤ by GitHub

還有另一種不需要被數學公式的解法

在 1 到 x 之間，使用 binary search 來找

kotlin，time complexity = O(logN)

	class Solution {
	fun mySqrt(x: Int): Int {
	return if(x == 0) {
	0
	} else {
	var left = 1
	var right = x
	var mid = 0
	while(left < right) {
	mid = left + (right - left) / 2
	when {
	mid <= x / mid && (mid+1) > x / (mid+1) -> return mid
	mid > x / mid -> right = mid
	else -> left = mid + 1
	}
	}
	return left
	}
	}
	}

view raw sqrt_x.kt hosted with ❤ by GitHub