每次做題的時(shí)候都會(huì)發(fā)覺(jué)自己真是菜得一逼寺董,這不這道easy題就沒(méi)做出來(lái)失暂。
題目描述
在數(shù)字隊(duì)列1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11....
的無(wú)窮隊(duì)列里找到第nth個(gè)數(shù)绸硕,比如第11個(gè)數(shù)是數(shù)字0盯拱。
我(超)的(時(shí))解法
public class Solution {
public static int findNthDigit(int n) {
if (n <= 9) {
return n;
} else {
int x = 0, i = 1;
while (x <= n) {
x += count(i);
if (x == n) {
break;
}
if (x <= n) {
i++;
}
}
int off = x - n;
if (off != 0) {
return findNthDigitInNum(i, off);
} else {
return (i % 10);
}
}
}
public static int count(int num) {
int count = 1;
while (num / 10 != 0) {
num /= 10;
count++;
}
return count;
}
public static int findNthDigitInNum(int num, int nth) {
int x = 0, s = 10;
for (int i = 0; i <= nth; i++) {
x = num % 10;
num /= 10;
}
return x;
}
}
思路蠻簡(jiǎn)單瓢对,定一個(gè)變量初始值為0宴咧,每次加上新的數(shù)字的長(zhǎng)度拳喻,最后如果超出了給定的結(jié)果姜盈,就退回若干位去找該位上的數(shù)字低千,如果剛好等于給定的長(zhǎng)度,對(duì)當(dāng)前的數(shù)字求最低位馏颂。
在測(cè)試用例1000000000的時(shí)候超時(shí)了....沒(méi)想到什么好的解決方法示血,又無(wú)恥的去看了下Top Solution
Top Solution
Top Solution里的解法跟我的解法思想上是類似,但是他用了很不錯(cuò)的技巧
public int findNthDigit(int n) {
int len = 1;
long count = 9;
int start = 1;
while (n > len * count) {
n -= len * count;
len += 1;
count *= 10;
start *= 10;
}
start += (n - 1) / len;
String s = Integer.toString(start);
return Character.getNumericValue(s.charAt((n - 1) % len));
}
我的解法里是一個(gè)一個(gè)疊加數(shù)字的長(zhǎng)度救拉,他則是把相同位數(shù)的數(shù)字一次性減掉难审,這里效率高了很多。再看start += (n-1) / len
亿絮,這里的n-1是為了不跳到下一個(gè)數(shù)字去告喊,這個(gè)語(yǔ)句可以得出滿足條件的最后一個(gè)數(shù)字是什么。(n-1) % len
這個(gè)表達(dá)式的作用是求出最后一個(gè)數(shù)字是第幾位上的派昧,這里的n-1是因?yàn)?code>s.charAt()的開始下標(biāo)是0黔姜。
舉個(gè)列子,假設(shè)輸入:n=11
蒂萎,那么執(zhí)行上面這個(gè)表達(dá)式時(shí)(2-1) % 2
秆吵,即返回最大數(shù)字的第二位,此時(shí)start的值為10五慈,所以結(jié)果為0帮毁。