LeetCode 69. Sqrt(x)(xの平方根)



Leetcode 69 Sqrt



Achieve int sqrt(int x) function. Calculate and return the square root of x, where x is a non-negative integer. Since the return type is an integer, only the integer part of the result is retained, and the decimal part will be discarded. Example 1: enter: 4 Output: 2 Example 2: enter: 8 Output: 2 Description: 8 The square root of is 2.82842..., Since the return type is an integer, the fractional part will be discarded.
  1. 二分探索
  2. この質問は、バイナリ検索の4番目のバリアントのアプリケーションです。指定された値以下の最後の要素を見つけます
class Solution { public int mySqrt(int x) { //The result must be between [1, 2... sqrt(x)] the 'last' 'less than or equal to' element of the given value int num = (int)Math.sqrt(x) //The number of elements in the interval int len = 0 for(int i = 1 i <= num i ++) { len ++ } int left = 0, right = len - 1 while(left <= right) { int mid = left + (right - left) / 2 // Cannot be written as: ((mid+1)*(mid+1))> x to prevent overflow // mid is used as the subscript index, and the element starts with 1 if((mid + 1) > x / (mid + 1)) { right = mid - 1 } else if((mid + 1) <= x / (mid + 1)) { //Find the last element less than or equal to the given value if(mid == len - 1 || (mid + 2) > x / (mid + 2)) { return mid + 1 } else { left = mid + 1 } } } //If you enter 0, return 0 return 0 } }

画像