题目来源
淘汰游戏，先从前往后淘汰，再从后往前淘汰，每次都是每隔一个淘汰一个，问最后剩下什么数字。
我是记录了开始和结尾，不断改变更新，直到开始和结尾是一样的。
复杂度是O(logn)。
class Solution {
public:
int lastRemaining(int n) {
int curStart = 1, curEnd = n, interval = 1;
while (curStart != curEnd) {
int tmp = curStart;
if (((abs(curEnd - curStart)) / interval + 1) % 2 == 0) {
curStart = curEnd;
curEnd = tmp + interval;
}
else {
curStart = curEnd - interval;
curEnd = tmp + interval;
}
interval *= -2;
}
return curStart;
}
};
看了下讨论区，解法更加简洁明了。只记录最小的数字、间隔、剩余数字个数以及是否从左边开始。靠这些就可以对这些记录进行更新。直到剩余数字个数为1。
class Solution {
public:
int lastRemaining(int n) {
int curHead = 1, interval = 1, remaining = n;
bool isLeft = true;
while (remaining > 1) {
if (isLeft || remaining % 2 == 1)
curHead += interval;
remaining /= 2;
interval *= 2;
isLeft = !isLeft;
}
return curHead;
}
};
