--------------------------方法一:利用数组-------------------------
直接用数组做,经测试效率最高,10万人时耗时约30ms。
- package com.itheima;
- /**
- * 第10题:有100个人围成一个圈,从1开始报数,报到14的这个人就要退出。
- * 然后其他人重新开始,从1报数,到14退出。问:最后剩下的是100人中的第几个人?
- * @author zl
- *思路:
- *一,可以定义一个数组,数组的索引表示每个人的id,元素大小可以设为0和1,0表示数到14的出圈的人,1表示还在圈里;
- *二,定义count,表示当前报的数,具有累加性,定义在循环外;num表示在圈里剩下的人数;
- *三,定义嵌套循环,内循环表示遍历数组并进行判断剩余的人数;外循环一直执行直到剩余人数为1就跳出。
- *四,每次都要遍历完整个数组并进行判断,效率却很高,貌似是最高的。
- */
- public class Test10CricleCountArray {
- public static void main(String[] args) {
- long before = System.currentTimeMillis();
-
- int left = circleCount(100000);
- System.out.println("剩下的人的序号为:"+left);
-
- long after = System.currentTimeMillis();
- System.out.println(after-before);//为10000人时,耗时约30ms
- }
- public static int circleCount(int n) {
- int[] arr = new int[n];
- for(int i=0; i<arr.length; i++) {
- arr[i] = 1;//1表示在圈中,0表示出圈
- }
-
- int count = 0;//当前应该报的数
- int num = arr.length;//剩余人数
- while(num>1) {
- num = arr.length;//圈里剩下的人数(假设全部在圈内);
-
- for(int i=0; i<arr.length; i++) {
- if(arr[i]==0) {
- num --;//当前人已出圈
- } else {
- count ++;
- if(count == 14) {
- arr[i] = 0;
- count =0;
- num --; //当前人出圈
- }
- }
- }
-
- }
-
- //获取剩下的人的序号
- int left = 0;
- for(int i=0; i<arr.length; i++) {
- if(arr[i] == 1) {
- left = i+1; //索引从0开的,序号需加1!
- }
- }
-
- return left;
- }
- }
复制代码
--------------------------方法二:利用容器--------------------------
利用LinkedList时,经测试10万人时,耗时约40ms,与数组相当;
利用ArrayList时,经测试10万人时,耗时约400ms,效率最低。
ackage com.itheima;
import java.util.*;
/**
* 第10题:有100个人围成一个圈,从1开始报数,报到14的这个人就要退出。
* 然后其他人重新开始,从1报数,到14退出。问:最后剩下的是100人中的第几个人?
* @author zl
*思路:
*一:利用容器存储和删除人数;
*二:循环,容器长度为1时跳出,返回元素值;
*三:循环中,数数并删除元素。
*/
public class Test10CircleCountLink {
public static void main(String[] args) {
long before = System.currentTimeMillis();
int left = circleCount(100000);
System.out.println("剩下的人的序号为:"+left );
long after = System.currentTimeMillis();
System.out.println(after - before);
}
private static int circleCount(int n) {
//定义容器并初始化
List<Integer> list = new LinkedList<Integer>();//50000人时,耗时约40ms
// List<Integer> list = new ArrayList<Integer>();//50000人时,耗时400ms
for(int i=1; i<=n; i++) {
list.add(i);
}
int count = 0;//当前报数
//循环、判断并输出
while(list.size()>1) {
Iterator<Integer> ite = list.listIterator();
while(ite.hasNext()) {
ite.next();
count ++;
if(count==14) {
ite.remove();
count = 0;
}
}
}
return list.get(0);
}
}
以上二种方法,仅供参考。若大家有新的做法,欢迎多多交流,呵呵,~:)。
|
|