剑指 Offer 62(圆圈中最后剩下的数字).约瑟夫环问题几种解决方法归纳

1. 题目介绍

约瑟夫是犹太军队的一个将军，在反抗罗马的起义中，他所率领的军队被击溃，只剩下残余的部队40余人，他们都是宁死不屈的人，所以不愿投降做叛徒。最后他提议，所有人围成一圈，从指定的一个人开始，顺时针报数，从1报数到3，每次报到3的那个人开枪自杀，之后从下一个人继续从1开始报数，直到最后只剩下一个人。

2. 循环链表解法

其实这道题很明显就是一个单向循环链表，我们只需要将这些人作为元素节点放入单向循环链表中，然后模拟报数即可首先，单向循环链表可以使用之前写的：单向循环链表


    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("输入人数：");
        int personAmout = input.nextInt();
        System.out.println("输入最大报数：");
        int number = input.nextInt();
        MyLinkedList list = new MyLinkedList();
        for (int i = 0; i < personAmout; i++) {
            list.add(i);
        }

        System.out.println(list.size+"人已经围成圈,假设从头开始数,报数从0到3");
        list.print();

        Node currentNode = list.first;
        Node preNode = null;
        StringBuffer stringBuffer = new StringBuffer("");
        while (currentNode.next != currentNode){
            //只需要报数往后数number-1次，因为第一次已经有了
            for (int i = 0; i < number - 1; i++) {
                preNode = currentNode;
                currentNode = currentNode.next;
            }
            stringBuffer.append(currentNode.data+"出局").append(",");
            preNode.next = currentNode.next;
            currentNode = currentNode.next;
        }
        System.out.println(stringBuffer.toString());
        System.out.println(currentNode.data+"存活");
    }

执行结果：

输入人数：
10
输入最大报数：
3
10人已经围成圈,假设从头开始数,报数从0到3
0 => 1
1 => 2
2 => 3
3 => 4
4 => 5
5 => 6
6 => 7
7 => 8
8 => 9
9 => 0
2出局,5出局,8出局,1出局,6出局,0出局,7出局,4出局,9出局,
3存活

ps:上面这个是使用自定义的单向循环链表来模拟的，事实上我们也可以使用jdk中的ArrayList来模拟

    public static int getLastByArrayList(int m,int n){
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < m; i++) {
            list.add(i);
        }

        //假设从第一个元素位置开始报数
        int current = 0;
        //每次循环里面条件成立,删除元素,直到只剩下一个元素
        while (m > 1){
            //每次要删除的就是当前元素位置加n-1之后的位置的元素,之所以要和m取余,是因为需要从最后一个元素到第一个元素进行一圈过渡,这里不是环形链表,所以使用这样的方式处理,这也是非常聪明的处理方式
            current = (current + n - 1) % m;
            list.remove(current);
            //每次删除后当前的圈人数就少了1
            m--;
        }
        return list.get(0);
    }

3.数学方法-反推求解

首先来看下面这张图

可以看出来,这就是一次次淘汰,然后从下一个重新开始报数的模型 ,按照这样的规律,不难知道,在最后一个的时候,只剩下一个元素,所以锁定到的那个需要出局的就是0索引位置的元素

也就是下面这张图片的N=1的时候，需要出局的就是0位置的元素

所以，如果使用函数F来表示最后生存下来的人在每一轮开始时的位置，我们可以得到一个已知条件，最后这个人的位置是0，即 F(1,m) = 0,在这里m=3，也就是F(1,3) = 0 ,所以，理论上，我们只要可以按照相反的操作，从最后一轮模拟出上一轮的位置顺序，然后就能最终递推出最开始的时候，

如下图

所以如果F(7,3) = 3,那么递推后可以得到F(8,3) = F(7,3) + 3
但这不时最终的通用递推结果，因为，比如最后一个情况

当前串复原后的串最大索引位置为1，右移3之后，当前串为3，所以在复原串中肯定是找不到位置的，肯定是继续从头开始转一圈，也就是求余,
所以(0+3)%2 = 1 所以最终的递推式子是这样的：
F(n,m) = (F(n-1,m) + 3) % n 也就是在向右移动三位之后再和复原串的长度取余（防止超出的情况，也就是一轮后过度的情况）

递归写法


    public static int getLast(int n,int m){
        if(n == 1){
            return 0;
        }else{
            return (getLast(n-1,m)+3)%n;
        }
    }

循环写法1

    public int getLast1(int n, int m) {
        int index = 0;
        //按照需要回退的次数
        for (int i = 0; i < n - 1; i++) {
            index = (index + m) % (i + 2);
        }
        return index;
    }

循环写法2

    public int getLast1(int n, int m) {
        int index = 0;
        //按照每次回退的长度递增，直到最后一次（即原始串）
        for (int i = 2; i <= n; i++) {
            index = (index + m) % i;
        }
        return index;
    }

4.总结

对于这几种方法，首先模拟法肯定效率较低，每次都需要报数m次，也就是每次都需要进行三次指针移动遍历，总共n个人，想剩下最后一个人，报数轮次是n-1次，所以时间复杂度是O(n*m),但是使用递推表达式的方法，那么就只需要计算n-1次即可，时间复杂度也就是O(n) ，可以发现，这效率提升简直了。
使用递归的求解方法，要注意，递归的深度太大的话可能会出现栈溢出，jvm默认的栈大小为1M

leetcode：

class Solution {
    public int lastRemaining(int n, int m) {
           return getLast(n,m);     
    }

    public  int getLast(int n,int m){
     int index = 0;
     for(int i = 0;i < n-1;i++)
     {
         index = (index + m) % (i + 2);
     }
     return index;
    }
}

class Solution {
    public int lastRemaining(int n, int m) {
           return getLast(n,m);     
    }

    public int getLast(int n,int m){
        if(n == 1){
            return 0;
        }else{
            return (getLast(n-1,m)+m)%n;
        }
    }
}

模拟

class Solution {
    public int lastRemaining(int n, int m) {
           return getLast(n,m);     
    }

    public  int getLast(int m,int n){
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < m; i++) {
            list.add(i);
        }

        //假设从第一个元素位置开始报数
        int current = 0;
        //每次循环里面条件成立,删除元素,直到只剩下一个元素
        while (m > 1){
            //每次要删除的就是当前元素位置加n-1之后的位置的元素,之所以要和m取余,是因为需要从最后一个元素到第一个元素进行一圈过渡,这里不是环形链表,所以使用这样的方式处理,这也是非常聪明的处理方式
            current = (current + n - 1) % m;
            list.remove(current);
            //每次删除后当前的圈人数就少了1
            m--;
        }
        return list.get(0);
    }
}

ps: 下一篇文章我们来探索下，只包含头节点的单向循环链表，包含头尾的单向循环链表，包含头尾的双向循环链表，包含头尾的双向链表，ArrayList，LinkedList对于解决这个问题效率分别是什么样的，要如何一步步优化

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为: 2023/10/22 13:49