LC.P390[消除游戏]

方法一：数学

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int lastRemaining(int n) {
        int head = 1, step = 1;
        boolean left = true;
        while (n > 1) {
            if (left || n % 2 != 0) {
                head += step;
            }
            step *= 2;
            left = !left;
            n /= 2;
        }
        return head;
    }
}
  • 时间复杂度：$O(log_2n)$
  • 空间复杂度：$O(1)$