约瑟夫环问题
2019-06-13 本文已影响0人
小马哒哒001
/**
* 0,1, … , n-1 这n个数字排成一个圈圈,从数字0开始每次从圆圏里删除第m个数字。
* 求出这个圈圈里剩下的最后一个数字
* @param n
* @param m
* @return
*/
public static int lastNum(int n, int m) {
if (n < 1 || m < 1) {
return -1;
}
List<Integer> list = new LinkedList<>();
for (int i = 0; i < n; i++) {
list.add(i);
}
// 要删除元素的位置
int idx = 0;
while (list.size() > 1) {
// 只要移动m-1次就可以移动到下一个要删除的元素上
for (int i = 1; i < m; i++) {
idx = (idx + 1) % list.size();
}
list.remove(idx);
}
return list.get(0);
}