Nte Ziffer – Leetcode Problem 400

Ursprünglicher Problemlink:https://leetcode.com/problems/nth-digit/description/

In dieser Aufgabe sollen wir die n-te Ziffer der unendlichen Folge finden, die als Zeichenfolge 1,2,3,4,5,6,7,8,9…

Zum Beispiel wäre die 3. Stelle 3, aber die 10. Stelle wäre 1 (die Zehnerstelle von 10) und die 11. Stelle wäre 0 (die Einerstelle von 10).

Bevor wir zu den Erklärungen kommen, der schnelle Ansatz, der 100 % der Einreichungen übertrifft, ist dieser, aber wir müssen ein bisschen Mathematik anwenden:

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) {
            return n;
        }
        long numOfDigits = 0;
        long power = 1;
        while (numOfDigits + (9 * (long)Math.pow(10, power - 1) * power) <= n) {
            numOfDigits += (9 * (long)Math.pow(10, power - 1) * power);
            power++;
        }
        long quotient = (n - numOfDigits) / power;
        long mod = (n - numOfDigits) % power;
        long i = mod == 0 ? (quotient + (long)Math.pow(10, power - 1) - 1) : (quotient + (long)Math.pow(10, power - 1));
        String num = String.valueOf(i);
        return mod == 0 ? Character.digit(num.charAt(num.length() - 1), 10) : Character.digit(num.charAt((int)mod - 1), 10);
    }
}

Also wechselte ich zum Durchschleifen und Berechnen der richtigen Zahl, aus der die n-te Ziffer stammen würde, wie folgt:

class Solution {
    public int findNthDigit(int n) {
        int i = 0;
        int prevIndex = 0;
        int index = 0;
        while (index < n) {
            i++;
            String num = String.valueOf(i);
            prevIndex = index;
            index += num.length();
        }
        String str = String.valueOf(i);
        return Character.digit(str.charAt(n - prevIndex - 1), 10);
    }
}

Der Weg, es schneller zu machen und es zu akzeptieren, bestand darin, die Lösung O(log n) zu machen, indem man wie folgt ein Muster dafür fand, wie viele Ziffern jeder Zahlenbereich generierte

Single digits 1-9 => 9 * 10^0 * 1 digits
Double digits 10-99 => 9 * 10^1 * 2 digits
...so the general formula is 9 * 10^(m - 1) * m digits for each number range

class Solution {
    public int findNthDigit(int n) {
        if (n < 10) {
            return n;
        }
        long numOfDigits = 0;
        long power = 1;
        while (numOfDigits + (9 * (long)Math.pow(10, power - 1) * power) <= n) {
            numOfDigits += (9 * (long)Math.pow(10, power - 1) * power);
            power++;
        }
        long quotient = (n - numOfDigits) / power;
        long mod = (n - numOfDigits) % power;
        long i = mod == 0 ? (quotient + (long)Math.pow(10, power - 1) - 1) : (quotient + (long)Math.pow(10, power - 1));
        String num = String.valueOf(i);
        return mod == 0 ? Character.digit(num.charAt(num.length() - 1), 10) : Character.digit(num.charAt((int)mod - 1), 10);
    }
}