题目：0, 1, … , n-1 这 n 个数字排成一个圈圈，从数字 0 开始每次从圆圏里删除第 m 个数字。求出这个圈圈里剩下的最后一个数字。
解法一
这里用LinkedList的性能比ArrayList的性能好，因为我们不断的要删除List中的某个元素。如果用ArrayList里面有大量的System.arraycopy。
public static void main(String[] args) {
System.out.print("list中原来的数字为: " + lastRemaining(10, 3));
}
public static int lastRemaining(int n, int m) {
LinkedList<Integer> list = new LinkedList<Integer>();
for (int i = 0; i < n; i++) {
list.addLast(i);
}
System.out.print("list中原来的数字为: ");
for (Integer inte : list) {
System.out.print(inte + ",");
}
System.out.println();
int index = 0;// list中元素的指针，list中的元素是从0开始计数的
while (list.size() > 1) {
for (int i = 1; i < m; i++) {// 让index增加m-1，
// index的值大于等于list中元素个数时，让index指向list的第一个元素，模拟循环链表
if (index >= (list.size() - 1)) {
index = 0;
} else {
index++;
}
}
list.remove(index);// 删除list中index处的元素
System.out.println("删除index为" + index + "的元素后剩下的元素是：");
for (Integer inte : list) {
System.out.print(inte + ",");
}
System.out.println();
}
return list.get(0);
}
结果：
list中原来的数字为: 0,1,2,3,4,5,6,7,8,9,
删除index为2的元素后剩下的元素是：
0,1,3,4,5,6,7,8,9,
删除index为4的元素后剩下的元素是：
0,1,3,4,6,7,8,9,
删除index为6的元素后剩下的元素是：
0,1,3,4,6,7,9,
删除index为1的元素后剩下的元素是：
0,3,4,6,7,9,
删除index为3的元素后剩下的元素是：
0,3,4,7,9,
删除index为0的元素后剩下的元素是：
3,4,7,9,
删除index为2的元素后剩下的元素是：
3,4,9,
删除index为1的元素后剩下的元素是：
3,9,
删除index为1的元素后剩下的元素是：
3,
list中原来的数字为: 3
解法二：
建造一个boolean数组，大小为总共数字的个数和，默认boolean数组的每个元素都是false，数到谁的时候，将数组对对应index的值改为true。知道最后只剩下一个元素值为false，得到此index。
private final static int COUNT_N = 10;
private final static int COUNT_M = 3; //
public static void main(String[] args) {
boolean[] bs = new boolean[COUNT_N];
/**
* count 的初始值是0，取值是1-COUNT_M。
*/
int removeCount = 0, count = 0, index = -1, arrIndex = -1;
System.out.println("起始：");
printLog(bs);
System.out.println("-----------------");
while (removeCount < bs.length - 1) {
arrIndex++;
if (arrIndex >= bs.length) {
arrIndex = 0;
}
if (!bs[arrIndex]) {
count++;
}
if (count >= COUNT_M) {
bs[arrIndex] = true;
printLog(bs);
count = 0;
removeCount++;
}
}
for (int i = 0; i < bs.length; i++) {
if (!bs[i]) {
index = i;
//打印最后一个数字的索引
System.out.println(index);
break;
}
}
}
private static void printLog(boolean[] bs) {
for (boolean b : bs) {
System.out.print(b + "\t");
}
System.out.println();
}
Paste_Image.png
