一道算法面试题

[leolin]

编程：数值增殖，给一个数字比如 4，增殖一次成 1 2 3 4，再增殖一次就是按照每个数字，再拓展成 1 到 X 的数列（ 1 1 2 1 2 3 1 2 3 4 ），然后问第 K 次形成的序列里第 P 位是多少？

[ppyybb]

我给一个思路吧，不知是否可行：
1. 分解问题，令 f （ x，k ）代表从数字 x 进行变换 k 次之后的数列长度，k 从 0 开始

2. f 的动态规划方程可以这样：
f （ x，k ）= f （ 1，k - 1 ）+ f （ 2，k -1 ）+ ... f （ x - 1，k - 1 ）
f （ x-1，k ）= f （ 1，k-1 ）+ ... f （ x-1，k-1 ）
所以有 f （ x，k ）= f （ x-1，k ）+ f （ x，k-1 ）
计算出来的复杂度是 O （ xk ），这是预处理的过程。

3. 假设需要查询位置 p，令 g （ x，k，p ）为题目所求，即变化后的数列的第 p 项，这个时候遍历 f （ 1，k-1 ），f （ 2，k-1 ）... f （ x，k-1 ）并维护当前数列的长度（也就是 sum ）
找到 p 所在的位置 t，假设前面长度为 sum，则问题可以直接规约到 g （ t，k-1，p - sum ）
这一步的时间复杂度是 O （ x ）

4. 不断递降可以将 k 降低到 1，一共需要 k 次，因此总复杂度是 O （ xk ）

5. 对于 k 为 1 的情况，结果是显然的。

6. 第三步的复杂度可以进一步降低，通过预处理求出 f 数列前缀和，那么可以进行二分查找找到第一个大于 p 的一项，降低为 logx

[LzyRapx]

用两个二分就可以了。

迭代 K 次可以看成形成 K 块，每块的长度为 i(1,2,3,4,5,....n), 因为前 i+1 块的和肯定是大于前 i 块的和的，也就是说是单调递增的，二分出是属于哪一块。最后在这一块里进行二分找出那一位数字就可以了。

简单就是：将找 112123123412345...的第 P 位转化为找 1234567891011...的第 P 位。
复杂度就是：O(logn * logn)

[firemiles]

@ppyybb #1 这个可行，要是递推公式能求出通项公式就更好了

[LzyRapx]

无聊写写，大概就是这样。

https://paste.ubuntu.com/p/fN8FkhWkbJ/

[ssynhtn]

这题在面试的时候是几乎不可能当场想出来的...
一个数 a 在经过 K 次增殖后形成的数列长度为 C(a+K-1, K) // a+K-1 中选 K 个数
1: 对于输入 X, 如果 X == C(j+K-1, K), 那么结果就是 j
2: 否则 let X = X - C(j+K-1, K), let K = K-1, 继续递归直到 1 成立为止

[ssynhtn]

https://paste.ubuntu.com/p/HGfttZMCw8/

[ppyybb]

@ssynhtn 如果只做到我在一楼给出来的程度是完全可以的。
推了下这个公式，大概思路是联想到类似杨辉三角的性质，然后引入组合数的性质 c （ n，k ）= c （ n-1，k ）+ c （ n-1，k-1 ），类似于一楼 f 的递推公式，然后想办法把 n 和 i 凑到这个组合数上面来就得到了结果。但是整个思路有点类似于靠猜想和凑的思路，不知道正解推导的思路是啥（硬算？）

[keith1126]

@ppyybb #7

目测可以用数学归纳法证明，不过结论还是靠观察猜出来的。

[ppyybb]

@keith1126 数学归纳法就更加靠猜测了，直接程度还不如我从杨辉三角联想到组合数的性质来推导，至少不太跳跃。

[LzyRapx]

能不能在短时间内想出来，不是看面试官给的 P 的范围吗？ P <= 10^9 和 P <= 10^18 完全可以是不一样的做法。

[ssynhtn]

@ppyybb
实际上我是通过 f(a, k) = Sum(f(j, k-1), 1<=j<=a)连续套用 k 次
得到 k 个下标的求和式 f(a, k) = Sum(1, 1<=j_1<=j_2<=j_3...<=j_k<=a)然后得到的

如果是递推的话, 对 K 是 1,2,3 的情况计算出公式后, 结合递推式, 熟悉组合数的性质的话也能直接就能看出长度公式

[ppyybb]

直观上的理解似乎是 a 个元素取 k 个数，但是这 k 个数又是可以重复的且存在全序关系，因此除了第一个数，再增加 k-1 个数，代表当每一个数需要选的和前一个数一样的那种可能？感觉不太严格，虽然结果肯定是对的

[charlie21]

直接上数学归纳法搞出公式完事

[xiadong1994]

面试里这种 x 变换之后求 y 位一般就是两种办法，要么是有通项公式的纯数学问题，要么是动态规划 /递推。

这题写几个例子就很容易想到第 k 层的长度是第 k-1 层元素的和，那么就可以用前缀和算出第 k 层的 p 位是第 k-1 层的哪一位（假设为 p_{k-1})扩展而来并且可知是 p_{k-1}扩展后的第几位。接下来问题就是第 k-1 层的第 p_{k-1}位是什么，以此类推。

而求每一层的分块长度就是基本的二维 DP，第 k 层的元素可以分成第 1 层（第一次增殖后）中元素（ 1,2,3...n ）分别增殖 k-1 次而来，因此 k 层 i 块长度就是 sum(dp[k-1][0], dp[k-1][1],...,dp[k-1][i])，因为是前缀和所以可以简化为 sum(dp[k-1][i], dp[k][i-1])。