约瑟夫环报数，直到剩下k-1人停止

梦里梦外; 2022-06-08 05:55 72阅读 0赞

## 题目 ##

> 有n个囚犯围成一圈从1到n编号，并从1开始报数。每当报到k，这个囚犯就会被执行死刑。接着从下一个人开始，剩下的囚犯继续从1开始报数并重复这个过程。直到所有囚犯的数目加起来小于k。问给定n和k，初始站在什么位置的囚犯能活下来？（k > 1 && k <=n)。

## Analysis ##

对于这道题目，首先我们应该明确当k输入非法的情况（既k<=1或k>n的情况，这两种情况下要么囚犯全部无法存活要么全部存活）。在这种情况下程序抛出异常以表示输入非法。

对于其余的情况，我们可以模拟整个循环报数的过程直到满足囚犯数目小于k为止。此时剩下的编号即为我们要求的编号。考虑到这种循环遍历且需要移除某个位置的元素的问题，`LinkedList`这种数据结构是比较适合的。因为我们在循环报数的过程中，一定是按顺序遍历的。所以只要利用`LinkedList`的`next`指针即可。同时考虑到移除当前元素后当前元素的前一个元素的`next`指针需要指向当前元素的后面一个元素，使用`DoubleLinkedList`能够大大简化这一过程的实现。同时考虑到这些囚犯是围成一个环，所以我们需要让链表的头尾相连形成一个环状链表。

事实上不使用循环链表而使用`Queue`的FIFO特性也可以实现这一模拟的过程。

### 时间复杂度 ###

考虑到我们需要不断循环整个链表，且每报k个数杀掉一个囚犯，且由于使用了双向链表，移除一个元素的时间为`O(1)`。因此每移除一个元素需要的时间为`k*O(1)=O(k)`。要循环到整个链表只剩`k-1`个元素，即删除了`n-（k-1)`个元素，那么总时间复杂度为`O(k)*(n-k+1)=O(nk)`。

实现如下：

public class JosephProblem {
        private static class Node {
            Node next;
            Node prev;
            int val;
    
            Node(int val) {
                this.val = val;
            }
        }
        public static List<Integer> josephSurviver(int n, int k) throws IllegalArgumentException {
            if (k <= 1 || k > n) {
                throw new IllegalArgumentException("k out of boundary!");
            }
    
            int size = n; 
            Node head = new Node(1);
            Node curr = head;
            for (int i = 1; i < n; i++) {
                curr.next = new Node(i + 1);
                curr.next.prev = curr;
                curr = curr.next;
            }
            // make the LinkedList a circle
            curr.next = head;
            head.prev = curr;
            curr = head;
    
            while (size >= k) {
                // Count off
                for (int i = 1; i <= k - 1; i++) {
                    curr = curr.next;
                }
    
                // Remove the kth element
                curr.prev.next = curr.next;
                curr.next.prev = curr.prev;
                size--;
    
                // Start from next person next time.
                curr = curr.next;
            }
    
            List<Integer> ret = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                ret.add(curr.val);
                curr = curr.next;
            }
    
            return ret;
        }
    }