约瑟夫问题

• OI Wiki: https://oi-wiki.org/misc/josephus/

题目	难度
1823. 找出游戏的获胜者	中等	从 1 到 n 编号
剑指 Offer 62. 圆圈中最后剩下的数字	简单	0 到 n-1

定义

n 个人标号 0,1,···,n-1。逆时针站一圈，从 0 号开始，每一次从当前的人逆时针数 k 个，然后让这个人出局。问最后剩下的人是谁。

1823. 找出游戏的获胜者

public class Solution1823 {
    public int findTheWinner(int n, int k) {
        return josephus(n, k) + 1;
    }

    // [0, n-1] 编号
    // k 较小 n 较大时。时间复杂度 O(klogn)
    private int josephus(int n, int k) {
        if (n == 1) {
            return 0;
        }
        if (k == 1) {
            return n - 1;
        }
        if (k > n) {
            return (josephus(n - 1, k) + k) % n;  // 线性算法
        }
        int res = josephus(n - n / k, k);
        res -= n % k;
        if (res < 0) {
            res += n;  // mod n
        } else {
            res += res / (k - 1);  // 还原位置
        }
        return res;
    }
}

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

public class SolutionO62 {
    public int lastRemaining(int n, int m) {
        return josephus(n, m);
    }

    // [0, n-1] 编号
    // k 较小 n 较大时。时间复杂度 O(klogn)
    private int josephus(int n, int k) {
        if (n == 1) {
            return 0;
        }
        if (k == 1) {
            return n - 1;
        }
        if (k > n) {
            return (josephus(n - 1, k) + k) % n;  // 线性算法
        }
        int res = josephus(n - n / k, k);
        res -= n % k;
        if (res < 0) {
            res += n;  // mod n
        } else {
            res += res / (k - 1);  // 还原位置
        }
        return res;
    }
}

（全文完）