题目描述

There is a list of sorted integers from 1 to n. 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 right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Example:

Input:
n = 9,
1 2 3 4 5 6 7 8 9
2 4 6 8
2 6
6

Output:
6

题意：给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。

算法1

(找规律)

题解：这道题其实是变种的约瑟夫循环问题。我们用$f(n)$代表将1 - n先从左到右再从右到左遍历最后剩下来的数字，用$b(n)$代表将1-n先从右到左，再从左到右遍历最后剩下来的数字。我们可以发现其中一些规律：
$$ f(1) = 1,b(1)=1 $$
$$ f(n) = 2 * b(n/2) $$
$$ f(n) + b(n) = n + 1 $$

• 规则1很好理解，是初始状态
• 规则2是因为，假设初始数组是[1,2,3,4,5,6]，最终剩下来的数字是$f(6)$，经过第一轮从左到右遍历后剩下来的是[2,4,6]，恰好是2 * [1,2,3]，但是这时候我们开始要从右侧开始遍历了，最终剩下来的数字是$b(3)$，我们可以发现$f(6) = 2 * b(3)$。如果初始数组长度为奇数也可以得到一样的结果。
• 规则3是因为，假设$f(n)$最终留下来的是从左到右的第$k$个数字，那么$b(n)$和$f(n)$是对称的操作，那么最后剩下来的肯定是从右到左的第$k$个数字，在这一题中二者相加之和是$n + 1$。

有了上面三个定理，答案就很好求解了，把公式3代入公式2可以得到：
$$ f(n) = 2 * b(n/2)\\ =2*(n/2 + 1 - f(n / 2))\\ $$
所以最终的代码可以写成：

    int lastRemaining(int n) {
        return n == 1 ? 1 : 2 * (n / 2 + 1 - f(n / 2));
    }