【LeetCode每日一题】400. 第 N 位数字【中等】

给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。

示例 1：

输入：n = 3 输出：3 示例 2：

输入：n = 11 输出：0 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。  

提示：

1 <= n <= 231 - 1 第 n 位上的数字是按计数单位（digit）从前往后数的第 n 个数，参见 示例 2 。

题解： 一开始就想到了最佳的解法，那就是直接算出第几位数字，但是写法有点丑陋，优化后的方案如下。

class Solution {
public:
    int findNthDigit(int n) {
        int digit = 1;
        long nine = 9;
        long count = 0;

        //按位数分组，并找到属于哪一组
        while(true){
            count = digit * nine;
            if(n <= count){
                break;
            }
            n -= count;
            digit++;
            nine *= 10;
        }
        
        //定位到数字
        long num = pow(10, digit - 1) + (n - 1) / digit;
        //定位到具体某个字符
        string strnum = to_string(num);
        char c = strnum[(n - 1) % digit];
        return (int)(c - '0');
    }
};

这种方法的时间复杂度是O(log10n)，非常高效，还有一种二分搜索的解法是我没有想到的。

class Solution {
public:
    int findNthDigit(int n) {
        int low = 1, high = 9;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            if (totalDigits(mid) < n) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        int d = low;
        int prevDigits = totalDigits(d - 1);
        int index = n - prevDigits - 1;
        int start = (int) pow(10, d - 1);
        int num = start + index / d;
        int digitIndex = index % d;
        int digit = (num / (int) (pow(10, d - digitIndex - 1))) % 10;
        return digit;
    }

    int totalDigits(int length) {
        int digits = 0;
        int curLength = 1, curCount = 9;
        while (curLength <= length) {
            digits += curLength * curCount;
            curLength++;
            curCount *= 10;
        }
        return digits;
    }
};