【Java】面試題44：數字序列中某一位的數字

題目：

數字序列中某一位的數字

數字以0123456789101112131415…的格式序列化到一個字元序列中。在這個序列中，第5位（從0開始計數）是5，第13位是1，第19位是4，等等。請寫一個函數求任意位對應的數字。

主要思路：

舉例分析，比如找第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。

按此規律，可求出其他數字。

關鍵點：位數的數值個數

時間複雜度：O(logn)，按位數進行查找

package jianZhiOffer;
/*
 * 面試題44：數字序列中某一位的數字
 * 題目：數字以012345678901112131415.。。的格式序列化到一個 字元序列中。
 * 再這個序列中，第5位（從0開始計數）是5，第13位是1，第19位是4，等等。
 * 請寫一個函數，求任意第n位對應的數字
 */
public class Demo44 {

	public static void main(String[] args) {
		System.out.println(digitAtIndex(1001));
	}
	
	private static int digitAtIndex(int index) {
		if(index<0)
			return -1;
		int digits = 1; //記錄目前數字的位數
		while(true) {
			int digitNumbers = countOfNumbersFor(digits); //目前位數的數值個數
			//數值乘上它的位數等于數字個數
			//比如，兩位數有90個（ 10-99），每個數值有2位數字，總數字個數為180
			int countOfNumbers = digitNumbers*digits;  //位數
			if(index<countOfNumbers) {
				return digitAtIndex(index,digits);
			 }else {
				//在下一位中查找
				index -= countOfNumbers;
				digits++;
			}
				
		}
	}
	
	//digits位數的數字個數
	//兩位數有9*10=90個（10-99），三位數有9*100=900（100-999）
	private static int countOfNumbersFor(int digits) {
		if(digits==1)
			return 10;
		int count = (int)Math.pow(10, digits-1);
		return 9*count;
	}
	
	//輸出對應的數
	private static int digitAtIndex(int index,int digits) {
		//對應的數值
		int number = beginNumberFor(digits) + index / digits;
		System.out.println(number);
		//數值右邊開始算的位置
		int indexFromRight = digits-index%digits;
		System.out.println(indexFromRight);
		
		//去除右邊的indexFromRight-1個數字
		for(int i=1;i<indexFromRight;i++)
			number /= 10;
		//求個位數字
		return number%10;
	}
	
	//digits位數的第一個數字，兩位數從10開始，三位數從100開始
	private static int beginNumberFor(int digits) {
		if(digits==1)
			return 0;
		
		return (int)Math.pow(10, digits-1);
	}

}