约瑟夫问题II

/**
 * 约瑟夫问题是一个著名的趣题。这里我们稍稍修改一下规则。有n个人站成一列。
 * 并从头到尾给他们编号，第一个人编号为1。然后从头开始报数，第一轮依次报1，2，1，2...然后报到2的人出局。接着第二轮再从上一轮最后一个报数的人开始依次报1，2，3，1，2，3...报到2，3的人出局。以此类推直到剩下以后一个人。现在需要求的即是这个人的编号。
 * <p>
 * 给定一个int n，代表游戏的人数。请返回最后一个人的编号
 */
时间复杂度O(nlog(n)) 空间复杂度n
/**
 * 思路：
 * 数组连表的思想，将数组当链表使用，删除某一位时将其值置0
 * 包含1个属性
 * int[] idArr:参与游戏的n个人的编号的数组
 *  
 * 每轮报数不等于1的人被淘汰，被淘汰的人对应值置为0，同时计数器减一；
 * 下一轮直接判断idArr[i]!=0的编号
 * 初始开始报数的索引位置是0，下一轮的第一个报数的人的索引为上一轮最后一个报1的人的索引
 * 每报一次1，就将begin指向该人的位置索引，这样就可以保证，begin总是指向一轮当中最后一个报1的人的位置索引
 * 直到计数器的值为1时结束递归，返回最后一名的索引值+1，即为最后一名的编号
 * 例子：1 2 3 4 5 6 7
 * 初始：
 * 1 2 3 4 5 6 7
 * begin=0
 * count=n
 * 第一轮结束：
 * 1 0 3 0 5 0 7
 * begin=6
 * count=4
 * 第二轮结束：
 *  0 0 0 0 5 0 7
 *  begin=4
 *  count=2
 *  第三轮结束：
 *  0 0 0 0 5 0 0
 *  begin=4
 *  count=1
 *  返回begin+1
 */
public int getResult(int n) {
        GameTable gameTable = new GameTable(n);
        int begin = 0, count = n, round = 2;
        int result = getResult(begin, gameTable, count, round, n);
        return result;
    }

    protected int getResult(int begin, GameTable gameTable, int count, int round, int n) {
        if (count == 1) {
            return begin + 1;
        }
        int k = 0, j = 0, i = begin;
        while (k < n) {
            if (gameTable.idArr[i] != 0) {
//                马上判断是否被淘汰
                if (++j != 1) {
                    gameTable.remove(i);
                    count--;
                } else {
                    begin = i;
                }
                if (j % round == 0) {
                    j = 0;
                }
            }
            i = (i+1) % n;
            k++;
        }
        return getResult(begin, gameTable, count, round + 1, n);
    }


    public static class GameTable {
        private int[] idArr;

        public GameTable(int n) {
            this.idArr = new int[n];
            initIdArr();
        }
        private void initIdArr() {
            for (int i = 0; i < idArr.length; i++) {
                idArr[i] = i + 1;
            }
        }

        /**
         * @param index 索引，被删除元素的索引
         * @return 被删除元素的值
         */
        public int remove(int index) {
            int value = idArr[index];
            idArr[index] = 0;
            return value;
        }
    }

*/

 public int getResult(int n) 
    {
        Stack<Integer> list = new Stack<Integer>();
        LinkedList<Integer> tempList = new LinkedList<Integer>();
        for(int i=n;i>=1;i--)
        {
            list.push(i);
        }
        int k = 1;
        while(true)
        {
            if(list.size()==1)
            {
                return list.pop();
            }
            while(!list.isEmpty())
            {
                tempList.push(list.pop());
                for(int j=0;j<k;j++)
                {
                    if(!list.isEmpty())
                    {
                        list.pop();
                    }
                }
            }
            int jundge = 0;
            while(!tempList.isEmpty())
            {
                if(jundge == 0)
                {
                    jundge = tempList.pollFirst();
                }
                else
                {
                    list.push(tempList.pollFirst());
                }                 }
            list.push(jundge);
            k++;
        }
    }

import java.util.*;

public class Joseph {
    public int getResult(int n) {
		return ysf(n, 2);
    }
    public int ysf(int n, int m) {
        int tmp = n%m==0 ? n/m : n/m+1;
        if(tmp <= m+1) {
            return (tmp-1)*m+1; //终止条件
        }
        int path = ysf(tmp, m+1); //m+1次时最后一人编号的位置
        return (path-2)*m + 1;
    }
}