摘要：對于這種會退出的情況，數(shù)組顯然不能像鏈表一樣直接斷開，因此采用標(biāo)記法先生成一個長度為的布爾型數(shù)組，用填充。中對整個進(jìn)行遍歷才能得到此時(shí)數(shù)組中的數(shù)量。

文中的速度測試部分，時(shí)間是通過簡單的 System.currentTimeMillis() 計(jì)算得到的，
又由于 Java 的特性，每次測試的結(jié)果都不一定相同，
對于低數(shù)量級的情況有 ± 20 的浮動，對于高數(shù)量級的情況有的能有 ± 1000 的浮動。

這道題本質(zhì)上是個約瑟夫環(huán)問題，最佳解法在最下面，本文只是探究一下數(shù)組暴力和鏈表的表現(xiàn)差異。

N 個人圍成一圈，順序排號。從第一個人開始報(bào)數(shù)（從1數(shù)到3），凡是到3的人退出圈子，問最后留下的是原來第幾號。

2 個人時(shí)留下的是第二個；

3個人時(shí)留下的是第二個；

5個人時(shí)留下的是第四個；

12個人時(shí)留下的是第十個；

100，000個人時(shí)留下的是第92620個人。

CPU Intel Xeon E3-1231 v3 @ 3.40GHz

RAM 16 GB

雖然第一反應(yīng)是用鏈表，但對于人數(shù)在1000以下的量級感覺數(shù)組也足以勝任，因此先用數(shù)組試試。

對于這種會 退出 的情況，數(shù)組顯然不能像鏈表一樣直接斷開，因此采用標(biāo)記法：

先生成一個長度為 N 的布爾型數(shù)組，用 true 填充。

報(bào)號時(shí)，對于報(bào)到 3 的位置，用 false 來標(biāo)記該位置，下次循環(huán)如果遇到 false 則可以直接跳過。

那么等到數(shù)組內(nèi)只剩一個 true 的時(shí)候，找到其位置，即是最后留下來的人的位置。

既然暴力，那干脆徹底一點(diǎn)：

    public static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         // 因?yàn)槭钦境梢粋€圓，所以在遍歷到最后時(shí)需要將下標(biāo)重新指向 0
           // count(map) 就是遍歷整個數(shù)組計(jì)算還剩余的 true 的數(shù)量
        for (int index = 0; count(map) > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            // 對于 false 可以直接跳過，因?yàn)樗鼈兿喈?dāng)于不存在
               if (! map[index]) continue;
             // 報(bào)號時(shí)如果不是3 則繼續(xù)找下一位;
            if (walk++ != 3) continue;
             // 如果是 3，則重置報(bào)號，并將當(dāng)前位置的值改為 false
            walk = 1;
            map[index] = false;
        }
        return find(map);
    }
    
    // 因?yàn)槭?count(map) == 1 的情況下才會調(diào)用這個方法，所以直接返回第一個 true 所在的位置即可
    public static int find(boolean[] map) {
        for (int i = 0; i < map.length; i++) {
            if (!map[i]) continue;
            return i + 1;
        }
        return -1;
    }

    public static int count(boolean[] map) {
        int count = 0;
        for (boolean bool : map) {
            count += bool ? 1 : 0;
        }
        return count;
    }；

對于這個解法，可以跑一下測試看看耗時(shí)：

很顯然，這種暴力的做法對于大一點(diǎn)的數(shù)量級就很吃力了，但是我又不想那么快就用鏈表，有沒有哪里是可以優(yōu)化的呢。

其實(shí)在前面的解法中，耗時(shí)操作有這么幾個：

findIndex 中不停得對整個 map 進(jìn)行遍歷，即便對于 false 直接跳過，但杯水車薪。

count 中對整個 map 進(jìn)行遍歷才能得到此時(shí)數(shù)組中 true 的數(shù)量。

find 中同樣需要對整個 map 進(jìn)行遍歷才能得到剩下的一個 true 的下標(biāo)。

其中第一點(diǎn)應(yīng)該是這種解法的本質(zhì)，沒什么好辦法，那么看看后兩點(diǎn)。

這個方法想做的事就是每次循環(huán)時(shí)檢查此時(shí)數(shù)組中 true 的數(shù)量是不是只剩一個了，因?yàn)檫@是循環(huán)的終結(jié)條件。

那么我們可以引入一個計(jì)數(shù)器：

    private static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         int countDown = N;
        for (int index = 0; countDown > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            if (! map[index]) continue;
            if (walk++ != 3) continue;
            walk = 1;
            map[index] = false;
               countDown -= 1;
        }
        return find(map);
    }

改成這種做法后，猜猜對于 100,000 這個數(shù)量級，這個暴力算法需要用時(shí)多久呢？

答案是 11 ms 。

對于 100,000,000 這個數(shù)量級，這個暴力算法仍只需要 3165 ms。

稍稍透露一下，后邊的鏈表解法在這個數(shù)量級的成績是 7738 ms，當(dāng)然可能是我太垃圾了，發(fā)揮不出鏈表的威力 Orz）

這個方法要做的是從整個數(shù)組中找到唯一的 true 的下標(biāo)，這同樣可以用一個外部變量來消除循環(huán)：

    private static int findIndex(final int N) {
        boolean[] map = new boolean[N];
        Arrays.fill(map, true);
        int walk = 1;
         // 記錄現(xiàn)在訪問到值為 true 的下標(biāo)
        int current = 0;
        int countDown = N;
        for (int index = 0; countDown > 1; index = (index == N - 1) ? 0 : (index + 1)) {
            if (! map[index]) continue;
            if (walk++ != 3) {
                   // 記錄最后一次遇到 true 的位置
                current = index;
                continue;
            }
            walk = 1;
            map[index] = false;
            countDown -= 1;
        }
         // 人的位置是從 1 開始數(shù)的，所以這里要加 1
        return current + 1;
    }

但是這個改動對速度的提升效果很小，對于 100,000,000 這個數(shù)量級，速度仍然在 3158 ~ 3191 ms 左右。

使用鏈表可以很方便得體現(xiàn) 退出 這個概念，鏈表的長度會隨著算法的進(jìn)行而越來越短直至剩下最后一個元素。因?yàn)闆]有 跳過標(biāo)記為 false 的步驟，理論上會比暴力數(shù)組解法要快。

    static class Node {
           // 當(dāng)前節(jié)點(diǎn)的下標(biāo)，即人的位置
        int index;
           // 上一個節(jié)點(diǎn)
        Node prev;
         // 下一個節(jié)點(diǎn)
        Node next;

        public Node (int index) {
            this.index = index;
        }

        public Node append(Node next) {
            this.next = next;
            next.prev = this;
            return next;
        }

         // 需要報(bào)號為3的人（當(dāng)前元素）退出時(shí)，從鏈表中斷開并將兩邊拼接起來
        public Node jump() {
            Node newNode = this.next;
            newNode.prev = this.prev;
            newNode.prev.next = newNode;
            this.prev = null;
            this.next = null;
            return newNode;
        }

        public static int findIndex(final int N) {
            Node root = new Node(1);
               // 初始化鏈表并賦值，這個過程對于很大的數(shù)量級而言速度肯定是慢過對數(shù)組的賦值的，
             // 畢竟類的實(shí)例化需要開銷。因此這段初始化不計(jì)入時(shí)間
            Node current = root;
            for (int i = 2; i <= N; i++) {
                current = current.append(new Node(i));
            }
            // 將首尾相連構(gòu)成循環(huán)列表
            current = current.append(root);
          
            long mills = System.currentTimeMillis();
          
            int COUNTER = N;
            int walk = 1;
            while (COUNTER > 1) {
                if (walk++ != 3) {
                    current = current.next;
                } else {
                    current = current.jump();
                    walk = 1;
                    COUNTER -= 1;
                }
            }

            System.out.println(System.currentTimeMillis() - mills);
            return current.index;

        }
    }

? 對于 1,000,000 及以上的數(shù)量級就沒測原數(shù)組暴力法了，太慢了...

可以看到，在百萬級別，改進(jìn)的數(shù)組暴力法已經(jīng)要比鏈表法快一半了，在億級要快的更多。

當(dāng)然這個速度差異很大程度上是因?yàn)殡S著數(shù)量級的加大，鏈表法所需要的內(nèi)存開銷已經(jīng)超出一個合理的范圍了，隨之而來的就是鏈表的斷開重組操作要比 標(biāo)記 重太多了。

但是這只是 想知道最后一個人的位置 的情況，數(shù)組的下標(biāo)可以做到一定程度的契合，如果情況更復(fù)雜了，顯然數(shù)組就不夠用了。

對于鏈表法在超大數(shù)量級的解法，感覺可以用多線程來做一次整體循環(huán)內(nèi)的截?cái)?，只是這樣復(fù)雜度就上去了，暫時(shí)不做了，有興趣的讀者可以自行嘗試一下。

    public static int josephus(int n) {
        int res = 0;
        if (n == 0) return 0;
        if (n < 3) {
            for (int i = 2; i <= n; i++) {
                res = (res + 3) % i;
            }
        } else {
            res = josephus(n - n / 3);
            if (res < (n % 3)) {
                res = res - (n % 3) + n;
            } else {
                res = res - (n % 3) + (res - (n % 3)) / 2;
            }
        }
        return res;
    }

    public static void main(String ...args) {
        System.out.println(hosephus(1000000000));
    }

這個解法對于一億這個數(shù)量級的運(yùn)算時(shí)間是不到 0 ms，來自我的 ACMer 同學(xué) ( 打不過正規(guī)軍啊，跪了

據(jù)我同學(xué)所說:

遞歸層數(shù) log 級別，n 可以達(dá)到 1e18 級別，15 ms 內(nèi)給出答案。