Sqrt(x)

描述

Implement int sqrt(int x).

Compute and return the square root of x.

分析

二分查找

代码

  1. // Plus One
  2. // 时间复杂度O(n)，空间复杂度O(1)
  3. public class Solution {
  4.     public int[] plusOne(int[] digits) {
  5.         return add(digits, 1);
  6.     }
  7.     private static int[] add(int[] digits, int digit) {
  8.         int c = digit;  // carry, 进位
  10.         for (int i = digits.length - 1; i >= 0; --i) {
  11.             digits[i] += c;
  12.             c = digits[i] / 10;
  13.             digits[i] %= 10;
  14.         }
  16.         if (c > 0) { // assert (c == 1)
  17.             int[] tmp = new int[digits.length + 1];
  18.             System.arraycopy(digits, 0, tmp, 1, digits.length);
  19.             tmp[0] = c;
  20.             return tmp;
  21.         } else {
  22.             return digits;
  23.         }
  24.     }
  25. };

相关题目

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/java/divide-and-conquer/sqrt.html