Leetcode 390消除游戏：O(n.log(n))解法优化求助

你的当前解法用数组模拟元素删除，每次remove_element操作要移动数组元素，时间复杂度是O(n)，加上递归每次处理的规模是n/2，总时间复杂度O(n log n)，当n较大时（比如3835）就会超时。根本问题在于没必要实际维护数组，我们可以用数学方法追踪剩余元素的规律，把时间复杂度降到O(log n)。

核心思路 #

每次交替删除后，剩余的元素都是一个等差数列。我们只需要追踪这个数列的三个关键参数：

• first：数列的首项
• step：数列的公差（每次删除后公差会翻倍）
• count：剩余元素的数量
• left：当前删除方向（从左到右/从右到左）

具体规则：

1. 从左到右删除：首项必然会被删掉，所以新的首项是first + step；公差翻倍（step *= 2）；剩余元素数减半（count = count / 2）。
2. 从右到左删除：
   • 如果剩余元素数是奇数：首项也会被删掉（比如1,2,3,4,5删完后剩2,4），新首项是first + step；
   • 如果剩余元素数是偶数：首项保留（比如1,2,3,4删完后剩1,3），首项不变；
   • 同样公差翻倍，剩余元素数减半。
3. 重复上述过程，直到剩余元素数为1，此时的first就是答案。

优化后的C代码 #

int lastRemaining(int n) {
    int first = 1;
    int step = 1;
    int count = n;
    bool left = true;
    
    while (count > 1) {
        if (left) {
            first += step;
        } else {
            // 从右往左删，只有count为奇数时才需要移动首项
            if (count % 2 == 1) {
                first += step;
            }
        }
        step *= 2;
        count /= 2;
        left = !left;
    }
    
    return first;
}

为什么这个解法高效？ #

每次循环count都会减半，循环次数是log2(n)级别，每次循环都是O(1)操作，总时间复杂度O(log n)，不管n多大都能快速运行。比如n=3835，只需要循环12次就能得到结果，完全不会超时。

对比你的原解法 #

原解法中，每次删除元素都要移动数组后面的所有元素，比如n=3835时，第一次删除就要移动近2000个元素，第二次再移动1000个，累计下来的时间开销非常大。而优化后的方法完全不需要数组操作，只靠几个变量的计算就能得到结果，效率提升几个数量级。

内容的提问来源于stack exchange，提问作者Akash Shanmugaraj