You have a list arr of all integers in the range [1, n] sorted in a strictly increasing order. Apply the following algorithm on arr:
- Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.
- Repeat the previous step again, but this time from right to left, remove the rightmost number and every other number from the remaining numbers.
- Keep repeating the steps again, alternating left to right and right to left, until a single number remains.
Given the integer n, return the last number that remains in arr.
Example 1:
Input: n = 9 Output: 6 Explanation: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] arr = [2, 4, 6, 8] arr = [2, 6] arr = [6]
Example 2:
Input: n = 1 Output: 1
Constraints:
1 <= n <= 109
消除游戏。
列表 arr 由在范围 [1, n] 中的所有整数组成，并按严格递增排序。请你对 arr 应用下述算法：
从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。
重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。
不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
给你整数 n ，返回 arr 最后剩下的数字。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/elimination-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题有点类似约瑟夫环问题，在 leetcode 很少见。我这里参考了一个总结的很好的思路。
注意题目的定义，对于一个长度为 N 的数列，假设
- f[i] 为在 连续序列 [1, i] 中进行「起始从左到右」的轮流换向间隔删除，最终左边剩余的编号
- f'[i] 为在 连续序列 [1, i] 中进行「起始从右到左」的轮流换向间隔删除，最终右边剩余的编号
可以得到一个公式 f[i] + f'[i] = i + 1
比如题目中的第一个例子，数列从 1 到 9，如果左起删除，最后最左边会是 2；如果右起删除，最后最右边会是 8。2 + 8 = 10 = 9 + 1。
接着，因为我们删除了一次之后，为了保持连续序列的定义，再下一次删除之前其实是要对剩余的数字进行重新编号的，比如第一次删除之后数列变成了 [2, 4, 6, 8, 10, x]，但是第二次删除的时候，其实我们是需要先把数组变成有序的才能去做删除的操作，即把数组变为 [1, 2, 3, 4, 5, x/2] - 这里取决于 x 是奇数还是偶数，但是差别不大了。此时我们得出第二个公式 f[i] = f'[i / 2] * 2。
如上两个公式我们可以合并为 f[i] = 2 * ( i/2 + 1 - f[i/2])。
时间O(logn)
空间O(1)
Java实现
1 class Solution {
2 public int lastRemaining(int n) {
3 return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2));
4 }
5 }