约瑟夫环问题多解法汇总

迈不过友情╰ 2021-09-21 01:34 282阅读 0赞

**【问题】**

首先，让小朋友们围成一个大圈。然后，随机指定一个数 m, 让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，并且不再回到圈中，从他的下一个小朋友开始，继续 0…m-1 报数… 这样下去… 直到剩下最后一个小朋友，哪个小朋友会在最后表演呢？(注：小朋友的编号是从 0 到 n-1)

如果没有小朋友，请返回 - 1

--------------------

**【题解一、数组模拟环】**

public int Solution1(int n, int m) { 
            if (n == 0) { 
                return -1;
            }
            int k,index,count;
            boolean[] flag = new boolean[n];
            k = 0; // 记录循环次数
            index = 0; // 游标，记录数组下标
            count = 0; // 记录跳出个数
            while (count < n-1) { 
                count ++;
                // 当k=m的时候，不进入循环
                while (k < m) { 
                    // 当前数值未出列，则循环次数+1，当前数值已出列，则不处理
                    if (!flag[index]) { 
                        // 跳出该数值
                        if (k == m-1) { 
                            flag[index] = true;
                        }
                        k++;
                    }
                    index ++;
                    if (index == n) { 
                        index = 0;
                    }
                }
                k = 0;
            }
            index = 0;
            while (index < n) { 
                if (!flag[index]) break;
                index ++;
            }
    
            return index;
        }

**PS:可以用list（arraylist或者linkedlist来代替普通数组、这类动态数组在该类问题上可以提升效率）**

--------------------

**【题解二、链表模拟】**

class ListNode { 
     
        int val;
        ListNode next = null;
     
        ListNode(int val) { 
            this.val = val;
        }
    }
     
    public class Solution { 
     	// 链表解法一
        public int Solution2(int n, int m) { 
     
            if (n <= 0 || m <= 0) { 
                return -1;
            }
     
            ListNode head = new ListNode(0);
            ListNode node = head;
            for (int i = 1; i < n; i++) { 
                node.next = new ListNode(i);
                node = node.next;
            }
            node.next = head;
     
            int k = 0;
            while (node.next != node) { 
                if (++k == m) { 
                    node.next = node.next.next;
                    k = 0;
                } else { 
                    node = node.next;
                }
            }
     
            return node.val;
        }
    
    	// 链表解法二
        public int Solution3(int n, int m) { 
            int index,count,k;
            // 建立链表
            ListNode p; // 链表游标
            ListNode head = new ListNode(0); // 表头
            p = head;
            index = 1;
            while (index < n) { 
                ListNode l = new ListNode(index);
                p.next = l;
                p = p.next;
                index ++;
            }
            p.next = head; // 构成闭环
    
            k = 0;
            p = head;
            // 当只有一个节点的时候跳出
           while (p.next != p) { 
               while (k < m - 2) { 
                   p = p.next;
                   k ++;
               }
               k = 0;
               // m-1的节点跳出
               p.next = p.next.next;
               // 把游标P点位到m位置
               p = p.next;
           }
            return p.val;
        }
     
    }

--------------------

**【题解三、数学算式】**

f(N,M) = ( f(N−1,M) + M ) % N

// 非递归
    public int Solution4(int n, int m) { 
            if (n <= 0 || m <= 0) { 
                return -1;
            }
            int num = 0;
            for (int i = 2; i <= n; i++) { 
                num = (num + m) % i;
            }
            return num;
        }
    
    // 递归算法
    public int Solution5(int n, int m) { 
            if (n <= 0 || m <= 0) { 
                return -1;
            }
    
            if (n == 1) return 0;
    
            return (Solution5(n-1,m) + m) % n;
        }