[剑指Offer]-圆圈中最后剩下的数字约瑟夫环问题

本文主要是介绍[剑指Offer]-圆圈中最后剩下的数字约瑟夫环问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

解题思路

• 创建一个总共有 n 个结点的环形链表，然后每次在这个链表中删除第 m 个结点。

算法图解

参考代码：

package offer;import java.util.LinkedList;
import java.util.List;/*** 圆圈中最后剩下的数字(约瑟夫环问题)* 题目：0, 1, … , n-1 这 n 个数字排成一个圈圈，从数字 0 开始每次从圆圏里删除第 m 个数字。* 求出这个圈圈里剩下的最后一个数字。*/
public class Offer62 {public static void main(String[] args) {System.out.println(lastRemaining(20, 3));}public static int lastRemaining(int n, int m) {if (n < 1 || m < 1) {return -1;}List<Integer> list = new LinkedList<Integer>();for (int i = 0; i < n; i++) {list.add(i);}// 要删除元素的位置int delIndex = 0;while (list.size() > 1) {// 只要移动m-1次就可以移动到下一个要删除的元素上for (int i = 1; i < m; i++) {delIndex = (delIndex + 1) % list.size();}list.remove(delIndex);}return list.get(0);}
}

---

附录

该题源码在我的 ?Github 上面！

这篇关于[剑指Offer]-圆圈中最后剩下的数字约瑟夫环问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---