Medium

题目描述

给你一个从 1 到 n 排序的整数列表。

对数组进行以下操作：

  1. 从左到右，删除第一个数字，然后每隔一个数字删除一个，直到列表结尾。
  2. 重复上面的步骤，但这次是从右到左。删除最右边的数字，然后每隔一个数字删除一个。
  3. 不断重复这些步骤，从左到右和从右到左交替进行，直到只剩下一个数字。

给你整数 n ，返回列表中最后剩下的数字。

示例 1：

输入：n = 9
输出：6
解释：
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
arr = [2, 4, 6, 8]
arr = [2, 6]
arr = [6]

示例 2：

输入：n = 1
输出：1

提示：

  • 1 <= n <= 10^9

解题思路

这道题可以通过递归或者数学方法来解决。

核心思路： 我们不需要真正模拟删除过程，而是找到规律。关键观察是：

  1. 从左到右删除时，剩余数组的第一个元素总是会被删除
  2. 从右到左删除时，只有当剩余元素个数为奇数时，第一个元素才会被删除

递归解法： 设 f(n, left) 表示对长度为 n 的数组，按照 left 方向（true表示从左到右）进行一轮删除后，最终剩下的数字相对于原数组起始位置的偏移。

递归关系：

  • 从左到右：f(n, true) = 2 * f(n/2, false)
  • 从右到左：
    • 如果 n 为奇数：f(n, false) = 2 * f(n/2, true)
    • 如果 n 为偶数：f(n, false) = 2 * f(n/2, true) - 1

迭代解法（推荐）： 我们可以直接模拟这个过程，维护剩余数组的起始位置、步长和长度：

  • 每次操作后，步长翻倍，长度减半
  • 根据删除方向和剩余元素个数的奇偶性来更新起始位置

代码实现

class Solution {
public:
    int lastRemaining(int n) {
        int start = 1;
        int step = 1;
        bool left = true;
        
        while (n > 1) {
            // 从左到右，或者从右到左且剩余个数为奇数时，起始位置需要更新
            if (left || n % 2 == 1) {
                start += step;
            }
            step *= 2;
            n /= 2;
            left = !left;
        }
        
        return start;
    }
};

class Solution:
    def lastRemaining(self, n: int) -> int:
        start = 1
        step = 1
        left = True
        
        while n > 1:
            # 从左到右，或者从右到左且剩余个数为奇数时，起始位置需要更新
            if left or n % 2 == 1:
                start += step
            step *= 2
            n //= 2
            left = not left
        
        return start

public class Solution {
    public int LastRemaining(int n) {
        int start = 1;
        int step = 1;
        bool left = true;
        
        while (n > 1) {
            // 从左到右，或者从右到左且剩余个数为奇数时，起始位置需要更新
            if (left || n % 2 == 1) {
                start += step;
            }
            step *= 2;
            n /= 2;
            left = !left;
        }
        
        return start;
    }
}

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

复杂度分析

复杂度类型值
时间复杂度O(log n)
空间复杂度O(1)

相关题目