最新要闻

广告

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

 警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

  1. 首页
  2. 移动通信
  3. 内容

环球今热点：2023-05-01：给你一个整数 n ， 请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。 1 ＜= n ＜=

来源：博客园


(资料图片仅供参考)

2023-05-01：给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...]中找出并返回第 n 位上的数字。1 <= n <= 2^31 - 1。输入：n = 11输出：0解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。

答案2023-05-01：

该程序的大体过程：

1.定义数组 under和 help，分别用于存储数字位数对应能处理的数的个数和指示各位数之间的跨度。

2.实现函数 findNthDigit，其输入为整数 n，表示要查找的数字在整数序列中的位置。根据 under数组，找到包含第 n 个数字的区间长度 len，并返回调用子函数 number的结果。

3.实现函数 number，其输入为当前路径 path、数字的位数 len、最高位的权重 offset、最低位的权重 all和从开始算起剩余的第几个数字 nth。如果 offset等于 0，则说明已经到达最低位，直接返回路径经过的值中的第 nth个数字；否则，计算出当前节点 cur取值（这可能需要根据 offset来进行特殊处理），根据 all和 offset计算下一个节点的路径 cur*(all/offset)+path，并递归地调用 number函数。

4.在 main函数中，定义一个整数变量 n表示要查找的数字在整数序列中的位置，调用 findNthDigit函数查找第 n个数字，并输出结果。

时间复杂度和空间复杂度如下：

1.findNthDigit函数中的循环需要遍历数组 under，时间复杂度为 O(1) 平均时间复杂度为 O(log n)；2. number函数实现了一个递归结构，每次递归除去常数项的时间复杂度为 O(1), 递归深度为 O(log n)，所以总时间复杂度为 O(log n)；3.数组 under和 help的空间复杂度分别为 O(1)，而递归调用 number函数时，栈空间的最大使用量也为 O(log n)。因此，总的空间复杂度为 O(log n)。

综上所述，该算法的时间复杂度和空间复杂度均为 O(log n)。

go完整代码如下：

package mainvar under = []int64{0, 9, 189, 2889, 38889, 488889, 5888889, 68888889, 788888889, 8888888889, 98888888889,}var help = []int{0,1,    // 110,   // 2100,  // 31000, // 410000,100000,1000000,10000000,100000000,1000000000,}func findNthDigit(n int) int {l := 0for i := 1; i < len(under); i++ {if under[i] >= int64(n) {l = ibreak}}return number(0, l, help[l], help[l], n-int(under[l-1]))}// path : 路径 左(低) <- 右(高)// len : n -> 5位数 len = 5 固定！// offset : 10000 目前要决定的是高1位// 1000 目前要决定的是高2位// 10 目前要决定的是高2位// 可变// all : 10000 固定// nth : 第几个func number(path, len, offset, all, nth int) int {if offset == 0 {return (path / help[nth]) % 10} else {j := (nth - 1) / (len * offset)cur := 0if offset == all {cur = 1}cur += jreturn number(cur*(all/offset)+path, len, offset/10, all, nth-j*len*offset)}}func main() {n := 11digit := findNthDigit(n)println(n, "th digit is", digit)}

rust完整代码如下：

static mut UNDER: [i64; 11] = [    0,    9,    189,    2889,    38889,    488889,    5888889,    68888889,    788888889,    8888888889,    98888888889,];static mut HELP: [i32; 11] = [    0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000,];fn find_nth_digit(n: i32) -> i32 {    let under: &[i64; 11];    let help: &[i32; 11];    unsafe {        under = &UNDER;        help = &HELP;    }    let mut len = 0;    for i in 1..under.len() {        if under[i] >= n as i64 {            len = i;            break;        }    }    number(0, len, help[len], help[len], (n - under[len - 1] as i32))}// path : 路径 左(低) <- 右(高)// len : n -> 5位数 len = 5 固定！// offset : 10000 目前要决定的是高1位// 1000 目前要决定的是高2位// 10 目前要决定的是高2位// 可变// all : 10000 固定// nth : 第几个fn number(path: i32, len: usize, offset: i32, all: i32, nth: i32) -> i32 {    let help: &[i32; 11];    unsafe {        help = &HELP;    }    if offset == 0 {        return (path / help[nth as usize]) % 10;    } else {        let j = (nth - 1) / (len as i32 * offset);        let cur = if offset == all { 1 } else { 0 } + j;        return number(            cur * (all / offset) + path,            len,            offset / 10,            all,            nth - j * len as i32 * offset,        );    }}fn main() {    unsafe {        let n = 11;        let digit = find_nth_digit(n);        println!("{}th digit is {}", n, digit);    }}

c完整代码如下：

#include const long under[] = {0L,     // 0位数，一共能解决几个位9L,     // 1位数，一共能解决几个位189L,   // 1~2位数，一共能解决几个位2889L,  // 1~3位数，一共能解决几个位38889L,488889L,5888889L,68888889L,788888889L,8888888889L,98888888889L};const int help[] = {0,1,      // 110,     // 2100,    // 31000,   // 410000,100000,1000000,10000000,100000000,1000000000};int findNthDigit(int n) {int len = 0;for (int i = 1; i < sizeof(under) / sizeof(long); i++) {if (under[i] >= n) {len = i;break;}}return number(0, len, help[len], help[len], n - under[len - 1]);}// path : 路径 左(低) <- 右(高)// len : n -> 5位数 len = 5 固定！// offset : 10000 目前要决定的是高1位// 1000 目前要决定的是高2位// 10 目前要决定的是高2位// 可变// all : 10000 固定// nth : 第几个int number(int path, int len, int offset, int all, int nth) {if (offset == 0) {return (path / help[nth]) % 10;}else {int j = (nth - 1) / (len * offset);int cur = (offset == all ? 1 : 0) + j;return number(cur * (all / offset) + path, len, offset / 10, all, nth - j * len * offset);}}int main() {int n = 11;int digit = findNthDigit(n);printf("%dth digit is %d\n", n, digit);return 0;}

c++完整代码如下：

#include using namespace std;const long under[] = {0L,     // 0位数，一共能解决几个位9L,     // 1位数，一共能解决几个位189L,   // 1~2位数，一共能解决几个位2889L,  // 1~3位数，一共能解决几个位38889L,488889L,5888889L,68888889L,788888889L,8888888889L,98888888889L};const int help[] = {0,1,      // 110,     // 2100,    // 31000,   // 410000,100000,1000000,10000000,100000000,1000000000};// path : 路径 左(低) <- 右(高)// len : n -> 5位数 len = 5 固定！// offset : 10000 目前要决定的是高1位// 1000 目前要决定的是高2位// 10 目前要决定的是高2位// 可变// all : 10000 固定// nth : 第几个int number(int path, int len, int offset, int all, int nth) {if (offset == 0) {return (path / help[nth]) % 10;}else {int j = (nth - 1) / (len * offset);int cur = (offset == all ? 1 : 0) + j;return number(cur * (all / offset) + path, len, offset / 10, all, nth - j * len * offset);}}int findNthDigit(int n) {int len = 0;for (int i = 1; i < sizeof(under) / sizeof(long); i++) {if (under[i] >= n) {len = i;break;}}return number(0, len, help[len], help[len], n - under[len - 1]);}int main() {int n = 11;int digit = findNthDigit(n);cout << n << "th digit is " << digit << endl;return 0;}

关键词：