java - 为什么要使用反向整数(Leet Code)O((log10(n)))解决方案？

有问题的problem要求反转32位带符号整数。这是Java中给定的解决方案：

    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

根据解决方案的解释，由于x中大约有log10（x）个数字，因此时间复杂度为O（log10（n））。直观上，while循环似乎有n-1次迭代，其中n是位数。 （即：7位数字需要进行6次迭代）。但是，该解决方案和给定的复杂度意味着n是整数本身，而不是位数。谁能帮助我直观地了解为什么上述解决方案是log10（n）？

最佳答案

Let's say the x = 123.

int rev = 0;

rev = rev * 10 + x % 10; // rev = 3,   1st iteration.

x = x/10;              // x = 12

rev = rev * 10 + x % 10;  // rev = 3 * 10 + 2 = 32,  2nd iteration

x = x/10;              // x = 1

rev = rev * 10 + x % 10;  // rev = 32 * 10 + 1 = 321, 3rd iteration.

x = 0 so the  loop terminates after 3 iterations for 3 digits.

循环中的条件检查以检查反转的值是否会超过32位数字可以容纳的值。

正是出于您在问题中所述的原因，它才是log10(n)。将数字n记录到给定基数的日志是将exponent升回到数字base所需的n。指数是数字中number of digits的近似值。

根据您的评论，也可以这样说：“对于任何数字n，其中m是number of digits in n，时间复杂度是O(m)。”

关于java - 为什么要使用反向整数(Leet Code)O((log10(n)))解决方案？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/59851998/