題目來源
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
題解分析
本題的解題關鍵是如何定位到指定字符所在的數字，通過仔細觀程式列數字串，可以發現，位數為1的數字個數為9，位數為2的數字個數為90，位數為3的數字個數為900，依次類推，
按照上述規律，可以進一步每種位數中包含的字符個數，它們是數字個數與位數的乘積，通過這種模擬法，可以首先求出所述字符是哪種位數的，進而根據除余運算可以計算出這個數字的具體指，最后，問題就轉換為了求解某個具體數字的某位上的字符，
演算法實作
class Solution {
public int findNthDigit(int n) {
// 9 * 1, 90 * 2, 900 * 3, 9000 * 4
int bit = 1;
long cnt = 9;
while (bit * cnt < n) {
n -= bit * cnt;
bit++;
cnt = cnt * 10;
}
// rest表示在bit位數集中的第幾字符位，減一是為了下標從0開始計算
int rest = (int) (n - 1);
// start表示bit位數集中的起始元素
int start = (int) Math.pow(10, bit-1);
// n是bit位數集中的第幾個元素
int pt = rest / bit;
// num表示第n個字符所在的元素
int num = start + pt;
// seq表示對應元素的第幾個字符（從左往右）
int seq = rest % bit;
// 后續問題轉換為求num數字的第seq個字符是什么，1203
// 去除第seq個字符后面數字后的結果
int left = num / (int) Math.pow(10, bit - seq -1);
return left % 10;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/540967.html
標籤：Java