一道算法面试题

• 資深大佬 : 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])。