约瑟夫环问题
数学解法
图中的绿色的线在新的一轮的开头是怎么指定的,每次都是固定地向前移位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 | public int lastRemaining(int n, int m) { |