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

示例：

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

输出:
6
Related Topics数学

通过常规方法编写程序，程序运行超时。

int count = 0;
List<Integer> list = new ArrayList<>();
for (int i = 1; i <= n; i++) {
    list.add(i);
}
while (true) {
    if (list.size() == 1) {
        break;
    }
    if (count % 2 == 0) {
        for (int i = 0; i < list.size(); i += 2) {
            list.remove(i);
            i--;
        }
    } else {
        for (int i = list.size() - 1; i >= 0; i -= 2) {
            list.remove(i);
        }
    }
    count += 1;
}
return list.get(0);

思路

提示使用数学进行解答，这里想到的就是使用递归。这里可以获取前面几个值。看能不能找到一些规律。其中f(n) 代表从左面开始的结果。 g(n)代表从右边开始的结果。

f(1) = 1 g(1) = 1

f(2) = 2 g(2) = 1

f(3) = 2 g(3) = 2

f(4) = 2 g(4) = 3

f(5) = 2 g(5) = 4

f(6) = 4 g(6) = 3

f(7) = 4 g(7) = 4

f(8) = 6 g(8) = 3

…… …….

由上面可以得到如下：

结果一：当n = 1 时 结果为 1。

规律一：f(n) + g(n) = n + 1

规律二：f(n) = g(n/2) * 2

由规律一得到：g(n) = n + 1 – f(n) 将该结果代入规律二中：

f(n) = (n/2 +1 – f(n/2)) *2

这样就可以写一个递归

代码：

    public int lastRemaining(int n) {
        if (n == 1) {
            return 1;
        } else {
            return (n / 2 + 1 - lastRemaining(n / 2)) * 2;
        }
    }