剑指offer面试题44：数字序列中某一位的数字（Java 实现）

题目：数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。请写一个函数求任意位对应的数字。

测试用例：

思路：按位数查找，时间复杂度为O（logn）

举例分析，比如找第1001位数字：

1. 1 位数的数值有10个：0~9，数字为10×1=10个，显然1001>10，跳过这10个数值，在后面找第991（1001-10）位数字。
2. 2 位数的数值有90个：10~99，数字为90×2=180个，且991>180，继续在后面找第811（991-180）位数字。
3. 3 位数的数值有900个：100~999，数字为900×3=2700个，且811<2700，说明第811位数字在位数为3的数值中。由于811=270×3+1，所以第811位是从100开始的第270个数值即370的第二个数字，就是7。
   按此规律，可求出其他数字。

public class test_forty_four {
    public int digitAtIndex(int index){
        if (index < 0)return -1;

        int digits = 1;  //表示位数（1为个位数、2为十位数...）

        while (true){
            //表示这个位数有多少个数字（1位数有10个、两位数是90个、三位数是900个）
            int numbersOfDigits = numberOfDigits(digits);

            //表示这个位数的数字总的位数（10*1、90*2、900*3）
            int totalNumbersOfDigits = numbersOfDigits * digits;

            //表示找到index位于哪个位数digits上
            if (index < totalNumbersOfDigits){
                return digitAtIndex(index, digits);
            }
            else {
                //直接跳过前面的数字
                index = index - totalNumbersOfDigits;
            }
            //继续查找下一个位数
            digits++;
        }
    }

    //找出这个位数有多少个数字
    private int numberOfDigits(int digits) {
        if (digits == 1)return 10;

        int count = (int)Math.pow(10, digits-1);
        return count*9;
    }

    //利用这个函数可以找到位于index的那位数
    private int digitAtIndex(int index, int digits) {
        //找到当前的数值，要求的index位数就是这个数值其中一位
        int number = beginNumber(digits) + index / digits;

        //从右边开始计数，看那位数处于数值的哪一个位置
        int indexFromRight = digits - index % digits;

        for (int i=1; i < indexFromRight; i++){
            number = number / 10;
        }
        //返回个位数的值，也是要找的那个数
        return number % 10;
    }

    private int beginNumber(int digits) {
        if (digits == 1){
            return 0;
        }else {
            return (int)Math.pow(10,digits-1);
        }
    }
}