出圈算法 | LichtMiao's Blog

问题：50人围成一圈，数3或3的倍数则出圈，问剩下的人是谁？在原来的位置是多少？
实现：

把数据填充到数组或链表。由于数组中元素不能自动向前移动，建议使用链表。链表每移除一位，数据会自动向前移一位（其实本质是链表删除一个元素，这个元素的前一个元素的指针会重新指到下一个元素）。
用一个while循环进行出圈，直到剩下一个元素。
注意如果使用下标0开始计算，则初始化时应使用-1，这样模拟元素已经少了一个。

import java.util.LinkedList;
import java.util.List;
public class Cycle {
	public static void main(String[] args) {
		System.out.println(cycle(50, 3));
	}
	/**
	 * 遇到k的倍数，则将其出圈
	 * @param total 总数
	 * @param k 倍数为k则出圈
	 * @return 最终留下的数
	 */
	public static int cycle (int total, int k) {
		List<Integer> list = new LinkedList<>();
		for (int i = 0; i < total; i++) { //将数据加到链表
			list.add(new Integer(i + 1));
		}
		int index = -1;
		while (list.size() > 1) {
			index = (index + k) % list.size();
			//由于链表每移除一位，数据会自动向前移，
			//所以需要将index-1才能保证删掉的是原来链表指定位置上的数
			//list.remove(index--); 
			list.remove(index);
			System.out.println(index + " " + (list.size()+1));
			index--;
		}
		return list.get(0).intValue();
	}
}

输出：