求无法执行插入操作后数组的第k大元素——竞赛算法问题求解

云原生阿岚

2026-5-9

解题思路：从数论角度快速解决这个数组扩展问题

我来帮你梳理下这个问题的核心解法，其实不用模拟整个插入过程（模拟的话效率极低，尤其是数组元素多的时候），关键是抓住数论里的GCD性质：

核心结论：最终数组的构成规律
反复插入两个元素的绝对差直到无法插入时，最终数组里的所有元素都是原数组所有元素的**最大公约数（GCD）**的倍数，而且是从这个GCD开始，到原数组最大值为止的所有连续倍数。
比如你给的例子[2,4,9]，原数组的GCD是1（gcd(2,4)=2，再和9算GCD得到1），最大值是9，所以最终数组其实是1到9的所有整数（你给出的只是中间步骤，还没完成所有插入）。
为什么这个结论成立？
这是因为两个正整数的绝对差的GCD，和这两个数本身的GCD是相等的——比如gcd(a, b) = gcd(a, |a - b|)。所以不管插入多少个新的差值，它们都是原数组GCD的倍数；而且最终会把所有这个倍数范围内的数都补全（可以通过辗转相除法的思路理解：只要有g，就能通过差值得到所有g的倍数）。
如何计算第k大元素？
1. 先算出原数组的全局GCD：迭代计算，先算前两个元素的GCD，再用这个结果和下一个元素算GCD，直到遍历完所有元素。
2. 找到原数组的最大值M：这个就是最终数组的上限，因为差值不可能超过原数组里的最大值。
3. 最终数组从小到大是[g, 2g, 3g, ..., M]，反过来从大到小排序就是[M, M-g, M-2g, ..., g]。所以第k大元素直接就是：
```
M - (k - 1) * g
```
4. 注意：最终数组的长度是M / g，题目里的k肯定是在这个范围内的（否则不存在第k大元素）。