题目大意：
消除游戏
给定一个从1 到 n 排序的整数列表。
首先，从左到右，从第一个数字开始，每隔一个数字进行删除，直到列表的末尾。
第二步，在剩下的数字中，从右到左，从倒数第一个数字开始，每隔一个数字进行删除，直到列表开头。
我们不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。
返回长度为 n 的列表中，最后剩下的数字。
示例：
输入: n = 9, 1 2 3 4 5 6 7 8 9 2 4 6 8 2 6 6 输出: 6
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=390
解题思路分析：
本题的关在在于寻找数组变化的规律。首先，不论从左至右还是从右至左删除数字，每次删除操作后数组中元素的个数都会减半，当数组只剩下一个数字时，该数字就是我们最终的答案。换句话说，每当数组减半之后，我们需要观察剩余数组中首位元素的值，直到剩余数组长度为1时，这个首位元素的值即是返回结果。
因为最先从左侧开始删除，因此，原数组的首位元素（最左侧）一定是会被删除的。当从右侧开始删除时，数组首元素（最左侧）是否会被删除，取决于当前数组长度，如果数组长度是偶数，首元素不会被删除，否则首元素会被删除。比如1，2，3，4，5，从右侧删除时，5，3，1会被删除，而当个数为偶数时，比如1，2，3，4，这时我们只会删除4和2，首元素1不会被删除。
因此，数组首元素被删除的可能有两种，第一，从左侧开始删除。第二，从右侧开始删除并且数组长度为奇数。
当首元素被删除后，剩余数组的首元素就会变为它被删除前的下一个元素，那么问题来了，我们如何得知下一个元素是谁？其实并不难，因为数组中的数字是存在规律的，初始时，数组中每两个数字之间间隔为1，进行一次删除后，间隔变为2，再经过一次删除后间隔变为4，间隔会成倍增长。只要我们知道当前经过了多少次删除操作，就能算出，两数之间的间隔，从而也就能知道被删除首元素的下一个元素的值。
实现代码：
public int lastRemaining(int n) {
// 数组中首元素
int firstNum=1;
// 数组中每两个数字间的差值
int diff=1;
// 是否为左起删除
boolean isLeft=true;
// 当元素个数大于1时，重复执行删除操作
while(n>1){
// 如果是左起删除，或者当前数组长度为奇数时，
// 首元素会被删除掉
if(isLeft || n%2==1){
// 新的首元素将是原首元素相邻的下一元素
firstNum+=diff;
}
// 删除操作后，数组元素个数减半
n/=2;
// 数组中相邻两数间的差值翻倍
diff*=2;
// 更换删除方向
isLeft=!isLeft;
}
// 返回最后剩下的首元素
return firstNum;
} 本题解法执行时间为3ms。
Runtime: 3 ms, faster than 54.75% of Java online submissions for Elimination Game.
Memory Usage: 37.6 MB, less than 33.33% of Java online submissions for Elimination Game.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-390-elimination-game-解题思路分析/