千锋扣丁学堂Java培训之索引值实现约瑟夫环算法

2019-05-07 13:21:42 2515浏览

今天千锋扣丁学堂Java培训老师给大家分享一篇关于Java通过索引值实现约瑟夫环算法的详细介绍，下面我们一起来看一下吧。

问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，

剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈

很多实现是使用链表结构，让元素构成一个圈，而我使用底层是数组的ArrayList集合实现，并且不需要遍历搜索，依靠数组特性：索引值，通过数学计算，让索引值构成一个圈，每次算出来的索引值，对应的那个元素一定是下一个出局的元素

这样的话，有n个元素，就只需要计算n次，删除n次，无需搜索，最大程度优化了程序的时间

import java.util.ArrayList;
import java.util.Scanner;
public class 约瑟夫环3 {
    public static void main(String[] args) {
        /*问题描述：N个人围成一圈，从第一个人开始报数，报到m的人出圈，
        剩下的人继续从1开始报数，报到m的人出圈；如此往复，直到所有人出圈*/
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();//n个人
        int m = sc.nextInt();//m号出列
        int count = m;
        ArrayList<Integer> list = new ArrayList<Integer>();
        for(int i = 1 ; i <= n ; i++){
            list.add(i);
        }
            for(; ;){
                if(list.size() == 1){
                    System.out.print(list.get(0) + " ");
                    return;
                }
                if(m <= list.size()){
                    System.out.print(list.get(m-1) + " ");
                    list.remove(m-1);
                    m += count -1;
                 
                }               
                if(list.size() < m){
                    m = m - list.size();
                }
            }
    }
}

以上所述是小编给大家介绍的Java通过索引值实现约瑟夫环详解整合，希望对大家有所帮助，

想要学好Java开发小编给大家推荐口碑良好的扣丁学堂，扣丁学堂有专业老师制定的Java学习路线图辅助学员学习，此外还有与时俱进的Java课程体系和Java视频教程供大家学习，想要学好Java开发技术的小伙伴快快行动吧。扣丁学堂Java技术交流群：850353792。

                          

      【关注微信公众号获取更多学习资料】         【扫码进入Python全栈开发免费公开课】

查看更多关于“Java开发资讯”的相关文章>>