LintCode领扣 题解:约瑟夫问题-阿里云开发者社区

开发者社区> 算法编程> 正文

LintCode领扣 题解:约瑟夫问题

简介: LintCode领扣 题解:约瑟夫问题

n个人按顺序围成一圈(编号为1~n),从第1个人从1开始报数,报到k的人出列,相邻的下个人重新从1开始报数,报到k的人出列,重复这个过程,直到队伍中只有1个人为止,这就是约瑟夫问题。现在给定n和k,你需要返回最后剩下的那个人的编号。

1<=n<=1000, 1<=k<=100
在线评测地址:[LintCode 领扣]:https://www.lintcode.com/problem/joseph-problem/?utm_source=sc-tc-sz)

样例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);
}

}
更多题解参见九章算法:https://www.jiuzhang.com/solution/joseph-problem/?utm_source=sc-tc-sz

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接