题目链接

无限长正整数排列字符串

题目描述

定义一个无限长的字符串 S，它是通过按顺序拼接所有正整数 1, 2, 3, 4, ... 得到的。 S = "123456789101112131415161718192021..." 给定一个整数 n，任务是找出并输出字符串 S 的第 n 个字符（下标从1开始）。

输入描述:

  • 在一行中输入一个整数 n。

输出描述:

  • 输出一个数字字符，表示 S 的第 n 个字符。

示例:

  • 输入: 3
  • 输出: '3' (S="123...")
  • 输入: 11
  • 输出: '0' (S="1234567891011...")

解题思路

这道题的核心是数学分析，而非字符串模拟。由于 n 可能非常大，直接构建字符串会导致超时或内存溢出。我们需要找到一种方法来直接计算出第 n 个字符属于哪个数字，以及是那个数字的第几位。

我们可以将这个无限字符串 S 按整数的位数（长度）进行分块：

  • 1位长数字: 1-9。共 9 个数，每个数长 1 位。占了 9 * 1 = 9 个字符。
  • 2位长数字: 10-99。共 90 个数，每个数长 2 位。占了 90 * 2 = 180 个字符。
  • 3位长数字: 100-999。共 900 个数，每个数长 3 位。占了 900 * 3 = 2700 个字符。
  • d位长数字: 到 。共 9 * 10^(d-1) 个数，每个数长 d 位。占了 d * 9 * 10^(d-1) 个字符。

基于这个模式，我们可以设计一个算法：

  1. 定位区间（Locate the Block）: 我们的目标是确定第 n 个字符落在哪个位数的数字块中。我们可以用一个循环来做这件事：

    • 从 digits = 1（1位数）开始。
    • 计算当前位数块的总字符数 length = digits * count（count 是当前位数的数字个数）。
    • 如果 n > length，说明第 n 个字符不在当前块，我们就让 n 减去 length，然后进入下一轮循环（digits 加 1）。
    • 如果 n <= length，说明我们已经找到了正确的数字块，循环结束。

  2. 确定数字（Determine the Number）: 循环结束后，n 的值表示的是在当前位数（digits）的数字块内的 1-based 索引。

    • 当前块的起始数字是 start_num = 10^(digits-1)。
    • 我们可以计算出目标字符所在的数字是当前块的第几个数（0-based）：num_index = (n - 1) / digits。
    • 所以，包含目标字符的具体数字是：target_num = start_num + num_index。

  3. 确定数位（Determine the Digit）: 现在我们知道了是哪个数字，还需要知道是这个数字的哪一位。

    • 目标字符在该数字内的索引（0-based）是：digit_index = (n - 1) % digits。

  4. 提取结果（Extract the Result）: 将 target_num 转换为字符串，然后取出 digit_index 位置上的字符即可。

举例说明 (n=11):

  1. 定位区间:
    • digits = 1，count = 9，length = 9。n=11 > 9，所以 n 变为 11 - 9 = 2。digits 变为 2。
    • digits = 2，count = 90，length = 180。n=2 <= 180。循环结束。第11个字符在2位数的块里。
  2. 确定数字:
    • n 现在是 2，digits 是 2。
    • start_num 是 10。
    • num_index = (2 - 1) / 2 = 0。
    • target_num = 10 + 0 = 10。
  3. 确定数位:
    • digit_index = (2 - 1) % 2 = 1。
  4. 提取:
    • target_num 是 10，转为字符串是 "10"。
    • 取索引为 1 的字符，即 '0'。

代码

#include <iostream>
#include <string>
#include <cmath>

using namespace std;

int main() {
    long long n;
    cin >> n;

    long long digits = 1;      // 当前处理的数字的位数
    long long count = 9;       // 当前位数下有多少个不同的数字
    long long start_num = 1;   // 当前位数下的起始数字

    while (n > digits * count) {
        n -= digits * count;
        digits++;
        count *= 10;
        start_num *= 10;
    }

    // 确定目标字符所在的具体数字
    long long target_num = start_num + (n - 1) / digits;

    // 确定目标字符在该数字的第几位 (0-based)
    long long digit_index = (n - 1) % digits;

    // 提取该位数字
    string s_num = to_string(target_num);
    cout << s_num[digit_index] << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();

        long digits = 1;
        long count = 9;
        long startNum = 1;

        while (n > digits * count) {
            n -= digits * count;
            digits++;
            count *= 10;
            startNum *= 10;
        }

        long targetNum = startNum + (n - 1) / digits;
        long digitIndex = (n - 1) % digits;

        String sNum = String.valueOf(targetNum);
        System.out.println(sNum.charAt((int)digitIndex));
    }
}

n = int(input())

digits = 1
count = 9
start_num = 1

while n > digits * count:
    n -= digits * count
    digits += 1
    count *= 10
    start_num *= 10

# 确定是哪个数字 (//是整除)
target_num = start_num + (n - 1) // digits
# 确定是该数字的第几位 (0-based)
digit_index = (n - 1) % digits

s_num = str(target_num)
print(s_num[digit_index])

算法及复杂度

  • 算法: 数学、逻辑推导。
  • 时间复杂度: 。循环的次数取决于最终数字的位数，而数字的位数与 n 的对数成正比。
  • 空间复杂度: 。主要开销在于将最终找到的数字转换为字符串，其长度与 n 的对数成正比。其他变量都是常数空间。