问题描述：
十个猴子围成一圈选大王，依次1-3 循环报数，报到3 的猴子被淘汰，直到最后一只猴子成为大王。问，哪只猴子最后能成为大王？
方法一：Java链表
public class TestAll {
static Scanner scanner = new Scanner(System.in);
static int num;
static String str;
static LinkedList<String> list = new LinkedList<String>();
static LinkedList<String> result = new LinkedList<String>();
public static void main(String[] arg) {
input();
output();
}
private static void output() {
pushNum();
Iterator it = result.iterator();
while (it.hasNext()) {
System.out.print(it.next() + " ");
}
}
private static void pushNum() {
int i = 1;
while (list.size() > 0) {
// System.out.println(i+"!! ");
Iterator it = list.iterator();
while (it.hasNext()) {
String node = (String) it.next();
if (i == num) {
result.add(node);
it.remove();
i = 0;
}
i++;
}
}
}
private static void input() {
str = scanner.nextLine();
String[] tmp = str.split(" ");
num = Integer.parseInt(tmp[0]);
for (int i = 1; i < tmp.length; i++) {
list.add(tmp[i]);
}
}
}
方法二：数组
public class TimeTest {
public static void main(String[] args) {
int num = 10;
boolean[] array = new boolean[num];
for (int i = 0; i < num; i++) {
array[i] = true;
}
int index = 0;
int count = 0;
int n = num;
while (n > 1) {
if (array[index] == true) {
count++;
if (count == 3)
// 当count等于3时，就淘汰一个；
{
array[index] = false;
n--; // 当有一个被淘汰时，n--；
count = 0;
}
}
index++;
// 当从0循环到29时，重新置index为0；
if (index == num) {
index = 0;
}
}
for (int i = 0; i < num; i++) {
if (array[i] == true)
System.out.println(i + 1);
}
}
}
其中方法一的时间复杂度为O（n^2）
方法二的时间复杂度为O(n)