分享一个暴力解法
n 个人按顺序围成一圈(编号为 1~n),从第 1 个人从 1 开始报数，报到 k 的人出列，相邻的下个人重新从 1 开始报数，报到 k 的人出列，重复这个过程，直到队伍中只有 1 个人为止，这就是约瑟夫问题。现在给定 n 和 k，你需要返回最后剩下的那个人的编号。 1<=n<=1000, 1<=k<=100
→戳此在线评测
样例 1 输入: n = 5, k = 3 输出: 4 解释: 求解过程： 原队列 ：1 2 3 4 5 第一轮：1 2 4 5 其中 3 出列 第二轮：2 4 5 其中 1 出列 第三轮：2 4 其中 5 出列 第四轮：4 其中 2 出列
样例 2 输入: n = 5, m = 1 输出: 5 解释: 第一轮：2 3 4 5, 其中 1 出列 第二轮：3 4 5, 其中 2 出列 第三轮：4 5, 其中 3 出列 第四轮：5, 其中 4 出列
[题解] 暴力解决。建立一个链表，并在每次迭代中删除一个节点。O(n)时间复杂度。 public class Solution { /** * @param n: an integer * @param k: an integer * @return: the last person's number */ public int josephProblem(int n, int k) { List<Integer> list = new LinkedList<>(); for (int i = 1; i <= n; i++) { list.add(i); } int i = 0; while (list.size() != 1) { i = (i + k - 1) % list.size(); list.remove(i); } return list.get(0); } }
点击解锁更多题解