62-圆圈中最后剩下的数字
小于 1 分钟
0,1,···,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字(删除后从下一个数字开始计数)。求出这个圆圈里剩下的最后一个数字。
例如,0、1、2、3、4这5个数字组成一个圆圈,从数字0开始每次删除第3个数字,则删除的前4个数字依次是2、0、4、1,因此最后剩下的数字是3。
模拟解法
使用数组进行模拟。
public int lastRemaining2(int n, int m) {
List<Integer> data = new ArrayList<>();
for (int i = 0; i < n; i++) {
data.add(i);
}
int totalSize = data.size();
int idx = 0;
for (int i = 1; i <= totalSize - 1; i++) {
int size = data.size();
int gap = m % size;
int removeIdx = (idx + gap - 1) % size;
if(removeIdx == -1 ){
removeIdx = size - 1;
}
data.remove(removeIdx);
idx = removeIdx == size - 1 ? 0 : removeIdx;
}
return data.get(0);
}
数学方法
通过数学可以得到一个计算这道题的公式,秒杀之。
public int LastRemaining_Solution(int n, int m) {
if(n < 1 || m < 1){
return -1;
}
int last = 0;
for (int i = 2; i <= n; i++) {
last = (last + m) % i;
}
return last;
}