剑指 Offer 62. 圆圈中最后剩下的数字

LeetCode： 剑指 Offer 62. 圆圈中最后剩下的数字

约瑟夫环问题

1. 模拟法
2. 数学法

模拟代码

    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>(n);
        // 初始化
        for (int i = 0; i < n; i++) {
            list.add(i);
        }

        int index = 0;
        while (list.size() != 1){
            index = (index + m - 1) % list.size();
            list.remove(index);
        }

        return list.get(0);
    }

数学法代码

    public int lastRemaining(int n, int m) {
        // 反推， 最后一轮的下标为 0
        int ans = 0;

        // 最后一轮剩下 2 人，所有从 2 开始
        for (int i = 2; i <= n; i++) {
            // i 上一轮剩下的人数, 每轮去掉一个人
            ans = (ans + m) % i;
        }

        return ans;
    }

---

>> 解题思路