题目

有 n 个人围成一圈，顺序排号。从第一个人开始报数（从 1 到 3 报数），凡报到 3 的人退出圈子，问最后留下的是原来的几号。

解答

public class WinnerGame {
    public static void main(String[] args) {
        WinnerGame wg = new WinnerGame();
        System.out.println(wg.getWinner(758));
    }

    public int getWinner(int n) {
        // 剩余人数
        int count = n;

        // 从1-count给每个人编号，不使用第一位
        int[] person = new int[count + 1];
        person[0] = -1;

        for (int i = 1; i < person.length; i++) {
            person[i] = i;
        }

        // 从 1-count 循环计数
        int now = 1;
        // 从 1-3 循环计数
        int m = 1;

        // 只要剩余人数大于1，就一直循环
        while (count > 1) {
            // 如果数到3，就淘汰这个人
            if (m == 3) {
                for (int i = now; i < count - 1; i++) {
                    // 淘汰第now个人，后面的人往前移一位
                    person[i] = person[i + 1];
                }
                // 剩余人数减1
                count--;
                // 因为后面人往前移了一位，now应该不动
                // 但下面now总是会加1，所以此处减1抵消
                now--;
            }

            // 继续往后数，如果超过了剩余人数就回到第一个人
            if (++now > count) {
                now = 1;
            }

            // 1-3循环计数器也加1，如果数到4，就回到1
            if (++m > 3) {
                m = 1;
            }
        }

        // 最终第一个位置的人就是获胜者
        return person[1];
    }
}