--------------------------方法一：利用数组-------------------------
直接用数组做，经测试效率最高，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);
}
}
以上二种方法，仅供参考。若大家有新的做法，欢迎多多交流，呵呵，~:)。
|
|
收藏
淘帖
踩
