0%

约瑟夫环问题

约瑟夫环问题

力扣Offer62题

数学解法

图中的绿色的线在新的一轮的开头是怎么指定的,每次都是固定地向前移位m个位置

从最后剩下的3倒着看,可以反推出这个数字在之前每轮的位置,最后的这个3的下标是0
第四轮反推,补上m个位置,然后模上当时的数组大小2,位置是(0 + 3) % 2 = 1
第三轮反推,补上m个位置,然后模上当时的数组大小3,位置是(1 + 3) % 3 = 1
第二轮反推,补上m个位置,然后模上当时的数组大小4,位置是(1 + 3) % 4 = 0
第一轮反推,补上m个位置,然后模上当时的数组大小5,位置是(0 + 3) % 5 = 3

最后数字3的下标在初始下标就为3,
总结过程

(当前index + m) % 上一轮剩余数字的个数

1
2
3
4
5
6
7
8
public int lastRemaining(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人,所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}