圆圈中最后剩下的数字（Java实现）

向右看齐 2023-07-19 12:07 10阅读 0赞

## 圆圈中最后剩下的数字（Java实现） ##

题目：0,1,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例：

输入: n = 5, m = 3
    输出: 3

有名的约瑟夫问题，利用ArrayList来模拟环形链表解题：

package Day56;
    
    import java.util.*;
    
    /** * @Author Zhongger * @Description 0, 1, , n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 * * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。 * * @Date 2020.3.30 */
    public class LastRemainingSolution { 
        public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int n=scanner.nextInt();
            int m=scanner.nextInt();
            LastRemainingSolution solution = new LastRemainingSolution();
            System.out.println(solution.lastRemaining(n, m));
        }
        public int lastRemaining(int n, int m) { 
            if (n<1||m<1){ 
                return -1;
            }
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < n; i++) { 
                list.add(i);
            }
            int index = 0;
            while (n>1){ 
                index =(index +m-1)%n;
                list.remove(index);
                n--;
            }
            return list.get(0);
        }
    }