69.x的平方根

链接：69.x的平方根
难度：Easy
标签：数学、二分查找
简介：实现 int sqrt(int x) 函数。

题解 1 - cpp

• 编辑时间：2021-12-20
• 内存消耗：6MB
• 编程语言：cpp
• 解法介绍：二分查找。

class Solution {
   public:
    int mySqrt(int x) {
        long long l = 0, r = x, m;
        while (l < r) {
            m = (l + r + 1) >> 1;
            if (m * m <= x)
                l = m;
            else
                r = m - 1;
        }
        return l;
    }
};

题解 2 - typescript

• 编辑时间：2021-07-22
• 执行用时：76ms
• 内存消耗：39.8MB
• 编程语言：typescript
• 解法介绍：二分查找。

function mySqrt(x: number): number {
  let l = 1;
  let r = x;
  while (l <= r) {
    const mid = r + ((l - r) >> 1);
    const midNum = mid ** 2;
    if (midNum > x) r = mid - 1;
    else if (midNum < x) l = mid + 1;
    else return mid;
  }
  return l - 1;
}

题解 3 - cpp

• 编辑时间：2021-12-20
• 内存消耗：5.8MB
• 编程语言：cpp
• 解法介绍：二分查找。

class Solution {
   public:
    int mySqrt(int x) {
        double l = 0, r = x, m;
        while ((int)l != (int)r) {
            m = l + (r - l) / 2.0;
            if (m > x / m)
                r = m;
            else
                l = m;
        }
        return (int)l;
    }
};

题解 4 - javascript

• 编辑时间：2020-05-09
• 执行用时：80ms
• 内存消耗：35.4MB
• 编程语言：javascript
• 解法介绍：手动实现 Math.sqrt(),二分搜索。

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  if (x === 1) return 1;
  let right = x;
  let left = 1;
  let mid = (right >> 1) + (left >> 1);
  while (true) {
    console.log(mid);
    if (mid ** 2 <= x) {
      if ((mid + 1) ** 2 > x) return mid;
      else {
        left = mid;
        mid = (right + left) >> 1;
      }
    } else {
      right = mid;
      mid = (right + left) >> 1;
    }
  }
};

题解 5 - javascript

• 编辑时间：2020-05-09
• 执行用时：84ms
• 内存消耗：35.5MB
• 编程语言：javascript
• 解法介绍：调用自带 Math 函数即可。

/**
 * @param {number} x
 * @return {number}
 */
var mySqrt = function (x) {
  return Math.floor(Math.sqrt(x));
};