Hard

题目描述

给你一个整数 n。

我们从左到右将整数 1 到 n 写成一个序列。然后，交替应用以下两个操作，直到只剩下一个整数，从操作 1 开始：

  • 操作 1：从左开始，删除每个第二个数字。
  • 操作 2：从右开始，删除每个第二个数字。

返回最后剩余的整数。

示例 1：

输入：n = 8
输出：3
解释：
写 [1, 2, 3, 4, 5, 6, 7, 8] 序列。
从左开始，删除每个第二个数字：[1, 2, 3, 4, 5, 6, 7, 8]。剩余整数为 [1, 3, 5, 7]。
从右开始，删除每个第二个数字：[1, 3, 5, 7]。剩余整数为 [3, 7]。
从左开始，删除每个第二个数字：[3, 7]。剩余整数为 [3]。

示例 2：

输入：n = 5
输出：1
解释：
写 [1, 2, 3, 4, 5] 序列。
从左开始，删除每个第二个数字：[1, 2, 3, 4, 5]。剩余整数为 [1, 3, 5]。
从右开始，删除每个第二个数字：[1, 3, 5]。剩余整数为 [1, 5]。
从左开始，删除每个第二个数字：[1, 5]。剩余整数为 [1]。

示例 3：

输入：n = 1
输出：1
解释：
写 [1] 序列。
最后剩余整数为 1。

约束条件：

  • 1 <= n <= 10^15

解题思路

这是一个经典的约瑟夫问题变形。我们需要使用分治法来解决。

核心思路：

  1. 对于每次操作，我们需要跟踪三个关键信息：

    • 当前序列的起始位置（start）
    • 当前剩余元素的数量（length）
    • 当前的删除方向（left_to_right）

  2. 递归规律分析：

    • 从左删除时，起始位置总是需要更新
    • 从右删除时，只有当剩余长度为奇数时，起始位置才需要更新
    • 每次操作后，剩余长度变为原来的一半，步长翻倍

  3. 状态转移：

    • 如果从左删除 OR（从右删除且剩余长度为奇数），则起始位置需要向前移动一个步长
    • 新的步长 = 旧步长 × 2
    • 新的长度 = 旧长度 / 2
    • 删除方向取反

  4. 基础情况： 当长度为1时，返回当前起始位置。

这种方法避免了模拟整个删除过程，时间复杂度从O(n)降低到O(log n)，能够处理极大的输入。

代码实现

class Solution {
public:
    long long lastInteger(long long n) {
        return solve(1, n, true);
    }
    
private:
    long long solve(long long start, long long length, bool leftToRight) {
        if (length == 1) {
            return start;
        }
        
        // 需要更新起始位置的条件：从左删除 OR (从右删除且长度为奇数)
        if (leftToRight || length % 2 == 1) {
            start += (1LL << getStep(length));
        }
        
        return solve(start, length / 2, !leftToRight);
    }
    
    int getStep(long long length) {
        int step = 0;
        while (length > 1) {
            length /= 2;
            step++;
        }
        return step;
    }
};

class Solution:
    def lastInteger(self, n: int) -> int:
        def solve(start, length, left_to_right):
            if length == 1:
                return start
            
            # 需要更新起始位置的条件：从左删除 OR (从右删除且长度为奇数)
            if left_to_right or length % 2 == 1:
                step = get_step(length)
                start += 2 ** step
            
            return solve(start, length // 2, not left_to_right)
        
        def get_step(length):
            step = 0
            while length > 1:
                length //= 2
                step += 1
            return step
        
        return solve(1, n, True)

public class Solution {
    public long LastInteger(long n) {
        return Solve(1, n, true);
    }
    
    private long Solve(long start, long length, bool leftToRight) {
        if (length == 1) {
            return start;
        }
        
        // 需要更新起始位置的条件：从左删除 OR (从右删除且长度为奇数)
        if (leftToRight || length % 2 == 1) {
            start += 1L << GetStep(length);
        }
        
        return Solve(start, length / 2, !leftToRight);
    }
    
    private int GetStep(long length) {
        int step = 0;
        while (length > 1) {
            length /= 2;
            step++;
        }
        return step;
    }
}

var lastInteger = function(n) {
    let remaining = n;
    let leftToRight = true;
    let first = 1;
    let step = 1;
    
    while (remaining > 1) {
        if (leftToRight || remaining % 2 === 1) {
            first += step;
        }
        remaining = Math.floor(remaining / 2);
        step *= 2;
        leftToRight = !leftToRight;
    }
    
    return first;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度分析
时间复杂度O(log n) - 每次递归都将问题规模减半
空间复杂度O(log n) - 递归调用栈的深度为 log n