跳至主要內容

400. 第 N 位数字


400. 第 N 位数字open in new window

🟠   🔖  数学 二分查找  🔗 力扣open in new window LeetCodeopen in new window

题目

Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].

Example 1:

Input: n = 3

Output: 3

Example 2:

Input: n = 11

Output: 0

Explanation: The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.

Constraints:

  • 1 <= n <= 2^31 - 1

题目大意

给你一个整数 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 <= 2^31 - 1

解题思路

  1. 确定数字的位数

    • 计算在每个数字位数范围(1 ~ 9: 1 位、10 ~ 99: 2 位、100 ~ 999: 3 位等)中包含的数字总数,直到找到 n 位所在的范围。
    • 对于 k 位数字,范围内的数字总个数为 9 * 10^(k-1),且它们的总位数为 k * 9 * 10^(k-1)
  2. 找到目标数字

    • 确定 n 所在的具体数字范围后,计算出是哪个数字以及在这个数字中的具体位置。
    • 通过计算偏移量确定要返回的数字。

复杂度分析

  • 时间复杂度O(log_10 n),通过不断增加位数,最多会进行对数级别的计算。
  • 空间复杂度O(1),只使用了常数级别的额外空间,存储了少量变量。

代码

/**
 * @param {number} n
 * @return {number}
 */
var findNthDigit = function (n) {
	let digit = 1; // 当前位数
	let count = 9; // 当前位数的数字总数
	let start = 1; // 当前位数的起始数字

	// 找到 n 所在的位数范围
	while (n > count * digit) {
		n -= count * digit;
		digit++;
		count *= 10;
		start *= 10;
	}

	// 找到 n 所在的具体数字
	const num = start + Math.floor((n - 1) / digit);
	const index = (n - 1) % digit;

	// 转换数字为字符串以获取具体的第 n 位数字
	return Number(String(num)[index]);
};