难度: Medium
列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
给你整数 n ，返回 arr 最后剩下的数字。
示例 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 <= 109运行时间: 29 ms
内存: 16.2 MB
class Solution:
def lastRemaining(self, n: int) -> int:
left = True # True表示从左到右，False表示从右到左
remaining = n # 剩余元素的数量
step = 1 # 步长，初始为1
head = 1 # 当前范围的起始值
while remaining > 1:
if left or remaining % 2 == 1:
# 如果从左到右，或者剩余元素数量为奇数，则保留的元素是当前的head
head += step
step *= 2 # 步长翻倍
remaining //= 2 # 剩余元素数量减半
left = not left # 切换方向
return head
solution = Solution()
print(solution.lastRemaining(9)) # 输出: 6
print(solution.lastRemaining(1)) # 输出: 1
print(solution.lastRemaining(10)) # 输出: 5
这个题解采用了一种数学的方式来解决问题。对于原始的序列[1, 2, 3, ..., n]，在每一轮操作后，剩余的数字都是等差数列。因此，我们可以跟踪每一轮操作后剩余数字序列的第一个数字和公差。变量left表示当前轮次是否从左到右删除，remaining表示剩余元素的数量，step表示当前的公差，head表示当前序列的第一个元素。每次迭代，我们更新head和step，并将剩余元素数量减半，直到只剩下一个元素为止。
时间复杂度: O(log n)
空间复杂度: O(1)
class Solution:
def lastRemaining(self, n: int) -> int:
left = True # True表示从左到右，False表示从右到左
remaining = n # 剩余元素的数量
step = 1 # 步长，初始为1
head = 1 # 当前范围的起始值
while remaining > 1:
if left or remaining % 2 == 1:
# 如果从左到右，或者剩余元素数量为奇数，则保留的元素是当前的head
head += step
step *= 2 # 步长翻倍
remaining //= 2 # 剩余元素数量减半
left = not left # 切换方向
return head
solution = Solution()
print(solution.lastRemaining(9)) # 输出: 6
print(solution.lastRemaining(1)) # 输出: 1
print(solution.lastRemaining(10)) # 输出: 5
在每一轮操作中，由于每次都是从序列中删除一半的元素，序列中剩余的元素间的间隔（步长）自然会增加到原来的两倍。例如，如果初始序列是[1,2,3,4,5,6,7,8]，第一轮操作后，我们可能得到序列[2,4,6,8]，这时每个元素之间的间隔从1增加到了2。这种步长的更新是保证我们可以正确地计算出每轮操作后序列的新头部（head）。如果不更新步长，我们将无法正确地跟踪序列中的元素，这会影响到算法的正确性。
当`remaining > 1`时，意味着序列中还有多于一个元素，因此还需要继续进行删除操作。一旦`remaining`等于1，这表示序列中只剩下一个元素，没有更多元素可以删除，这个剩余的单个元素就是我们要找的答案。因此，循环可以在这一点停止，因为进一步的操作不会改变剩余元素的值。
从左到右删除时，无论如何都会删除第一个元素，因此需要更新`head`来指向原本的第二个元素，即`head`加上`step`。当元素总数为奇数时，无论从哪个方向开始，都会在最后一个操作中删除中间的元素，这会导致从右侧开始删除时第一个元素被删除（因为中间元素成了第一个元素），从而需要更新`head`。这种情况下，`head`的更新确保了无论删除操作的方向如何，我们都能正确地跟踪下一轮的开始元素。
每次操作都会从序列中删除一半的元素，无论是从左到右还是从右到左开始。例如，如果初始序列是[1,2,3,4,5,6,7,8]，第一次操作（无论开始方向）都会删除其中的四个元素（例如1, 3, 5, 7或者2, 4, 6, 8），因此剩余元素数量变为原来的一半。这种减半操作直接对应于每轮实际从列表中删除元素的过程，是算法减少问题规模并逐步向答案逼近的一种方式。