网站首页 文章专栏 约瑟夫环算法
前言 :面试新华三时,有个题目就是约瑟夫环,因为有点紧张写的不是很好,记录下应当怎么写,网上流传很多种写法,使用数组实现的,使用集合实现的都有。这里介绍两种的实现方式。 |
约瑟夫环:这个算法什么意思呢,有很多种说法,大体的意思就是,一群人围城一圈,每个人自带一个编号(比如1,2,3,4,5,6...),从第一个开始报数,报数报到m的人死掉,下一个人重新从1开始报数,再次报到m的人死掉,问最后一个存活的人的原始位置。
1,第一种实现方式,使用java自带的LinkedList实现,因为其是用链表实现的,可以直接remove掉,需要注意的是移除后索引会减少。
/** * 输入总人数,循环次数,返回原始对应的下标,注意返回的是下标,不是第几个,应当是第下标+1个人 * @param totalPeople * @param loopNum * @return */ public static Integer test2(Integer totalPeople,Integer loopNum){ LinkedList<Integer> people = new LinkedList<>(); for (int i = 0; i < totalPeople;i++){ people.add(i); // 每个元素的值就是原始下标 } int index = 0; while(people.size() > 1){ for(int i = 1;i < loopNum;i++){ // 注意这里,循环次数 if(index == people.size() - 1){ index = 0; // 循环到底后,从头再来 }else { index++; } } people.remove(index); } return people.get(0); // 移除完后只剩一个元素了,他的值就是原始的下标值 }
2,第二种实现方式是用数组实现,也很直观。
/** * 输入总人数,循环次数,返回原始对应的下标 * @param totalPeople * @param loopNum * @return */ public static Integer test(Integer totalPeople,Integer loopNum){ Boolean[] people = new Boolean[totalPeople]; // 定义一个布尔数组,长度为总人数 for(int i = 0; i < totalPeople;i++){ people[i] = true; // 使其每个元素都为true } int count = 0; // 定义计数器 int index = 0; // 定义数组索引 int aliveNum = totalPeople; // 定义剩余存活人数 while (aliveNum > 1){ // 如果剩余人数多于1个就继续循环杀人 if(people[index]){ // 如果这个位置的人是活的再去杀人 count ++; //计数器自增 if(count == loopNum){ // 如果数到循环次数了 count = 0; // 计数器置零 people[index] = false; // 杀掉该人 aliveNum --; // 存活人数减一 } } index ++; // 无论杀不杀人,都要自增 if(index == totalPeople){ // 如果到数组结尾了,就从头开始 index = 0; } } for(int i = 0;i < totalPeople;i++){ if(people[i]){ return i; // 循环这个数组,里面只有一个为true的,返回他的索引 } } return null; }
暂时就写这两种方式,还有其他方式实现,都是大同小异,如有其他方式实现可以给我留言。
版权声明:本文由星尘阁原创出品,转载请注明出处!