Java两种方法实现循环报数

问题描述：

十个猴子围成一圈选大王，依次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();

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;

if (array[i] == true)

system.out.println(i + 1);

 其中方法一的时间复杂度为o（n^2）

方法二的时间复杂度为o(n)