★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10298994.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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 的列表中，最后剩下的数字。

示例：

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

输出:
6

20ms

1 class Solution {
2     func lastRemaining(_ n: Int) -> Int {
3         return n == 1 ? 1 : 2 * (n / 2 + 1 - lastRemaining(n / 2))
4     }
5 }

28ms

 1 class Solution {
 2   func clear(lun: Int, lunCount: Int, lastNum: Int, n: Int) -> Int {
 3     let lastSpan = (1<<(lun - 1))
 4     var tmpLastNum = lastNum
 5     
 6     if lun % 2 == 0 || (n / lastSpan) % 2 != 0 {
 7       tmpLastNum = tmpLastNum - lastSpan
 8     }
 9     
10     if lun == lunCount { return tmpLastNum }
11     return clear(lun: lun + 1,
12                  lunCount: lunCount,
13                  lastNum: tmpLastNum,
14                  n: n)
15   }
16   
17   func lastRemaining(_ n: Int) -> Int {
18     if n == 1 { return 1 }
19     var lunCount = 0
20     var total = n
21     while total != 1 {
22       total = total / 2
23       lunCount += 1
24     }
25     return clear(lun: 1,
26                  lunCount: lunCount,
27                  lastNum: n,
28                  n: n)
29   }
30 }