Почему это решение для обратного целого числа (Leet Code) O ((log10 (n))? - PullRequest
Новая
       22

Почему это решение для обратного целого числа (Leet Code) O ((log10 (n))?

0 голосов
/ 22 января 2020

Проблема , о которой идет речь, просит обратить 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;
    }
}

Согласно объяснению решения, сложность по времени составляет O (log10 (n)), потому что в x есть примерно log10 (x) цифр. Интуитивно понятно, что в то время как l oop, где n - число цифр, n-1 итераций. (IE: число 7 di git требует 6 итераций). Однако решение и заданная сложность подразумевают, что n - это само целое число, а не количество цифр. Может кто-нибудь помочь мне получить интуитивное понимание того, почему вышеприведенное решение является log10 (n)?

Ответы [ 2 ]

3 голосов
/ 22 января 2020

Если x - целое число, то floor (log10 (x)) + 1 равно количеству цифр в x.

Пусть log (10) x = некоторое число y. Тогда 10 ^ y = x.
Например, 

log(10) 10 = 1   
log(10) 100 = 2  
log(10) 1000 = 3 
...

Когда x не является совершенной степенью 10: 

floor( log(213) ) = 2

Дайте мне знать, если это не отвечает ваш вопрос.

0 голосов
/ 22 января 2020 
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.

Условные выражения в проверке l oop проверяют, не превысят ли обратные значения то, что может содержать 32-битное число.

Так что log10(n) точно по той причине, которую вы указали в ваш вопрос. Лог числа n для данной базы - это exponent, необходимый для возведения base обратно в число n. И показатель степени является приближением number of digits в числе.

На основании вашего комментария можно было бы также сказать, что «Для любого числа n, где m - это number of digits in n, сложность времени O(m). "

...