【剑指offer-Java版】45圆圈中最后剩下的数字

川长思鸟来 2022-08-21 10:46 127阅读 0赞

圆圈中最后剩余的数字:约瑟夫环问题  
0-n这n个数字排成一圈，从数字零开始每次从这个圆圈中删除第m个数字，求出剩余的最后一个数字

public class _Q45<T> {
    
        // 低效的模拟而已
        public int LastRemaining(int n, int m){
            if(n < 0 || m < 0) return -1;
    
            int circle[] = new int[n];
            for(int i=0; i<n; i++){
                circle[i] = i;
            }
    
            int count = 0;
            int time = 0;
            for (int i = 0; i < n; i++) {
    
                if (circle[i] != -1) {
                    count++;
                    if (count == m) {
                        circle[i] = -1;
                        count = 0;
                        time++;
                    }
                }
    
                if ((i == n - 1)  && (time != (n-1)))
                    i = -1;
            }
            int result = 0;
            for(int i=0; i<n; i++){
                if(circle[i] != -1){
                    result = circle[i];
                    break;
                }
            }
    
            return result;
        }
    
        // 采用映射的方法：
        /*
         * 对于原始 0 - n数据，删除第m个数，被删除的数字为(m-1)%n,将该数记为k ，那么剩余数字为
         * 0 1 2 .. m-2 m m+1 ... n-1
         * 新的计数起点为 m.
         * 
         * 将每次被删除的数字记为m 和 n的一个函数，那么 k = f(n,m)
         * 删除一个数字之后，原序列如果不变的话，是不能继续使用f的，因为f中关于n的序列是从0-n
         * 因此剩余序列中删除的下一个数字可以用g(n,m)来表示 -- 显然已经破坏了递归的条件
         * 
         * 为了使删除下一个数字时仍然可以使用f函数，可以将删除一个数字之后的序列做一个映射，以删除第一个数字之后的序列为例
         * m   -> 0
         * m+1 -> 1
         * ...
         * n-1 -> n-m-1
         * 0   -> n-m
         * 1   -> n-m+1
         * ...
         * m-2 -> n-2
         * 映射函数记为p，是关于x的一个函数p(x) = (x-m)%n 其中x取[0, m-2]并[m, n-1]
         * 该函数最终的值是最后剩余数字的映射后的编号，因此该函数的逆即为最后剩余数字实际编号
         * 其逆为： p`(x) = (x+m)%n
         * 
         * g(n-1, m) = p`(f(n-1, m)) = (f(n-1, m) + m)%n = f(n, m)
         * 注意该公式第一个等号成立的原因：
         * 该等号左侧函数代表在不是从0开始的序列中删除第m个元素
         * 右侧函数代表从0开始的n-1个元素中删除第m个元素，由于删除前都对这些元素做了映射，因此对于最后结果求逆，得出最后剩余元素的实际编号
         * 根据实际经验，无论是每次重新从0开始删除还是每次从新的被删除元素的下一元素开始删除，最终结果是相等的 -- 其实还是存在严格的数学证明
         * 
         * 第二个等号只是把参数带入而已 x = f(n-1, m)
         * 
         * 第三个等号成立的原因是 g(n-1, m) = f(n, m)
         * 
         * 最终得到递归等式：
         * f(n, m) = (f(n-1, m) + m) % n 其中变量为n;而m其实可以看做是常量
         * 当n 取为1的时候就代表只剩下最后一个数字，即为所求 -- 当然n == 1也就是递归的出口;不过不使用递归直接用循环也可以
         * 
         */
        // 非递归版本
        public int LastRemainingV2(int n, int m){
            if(m < 1 || n < 1) return -1;
    
            int last = 0;
            for(int i=2; i<=n; i++){
                last = (last + m) % i;
            }
    
            return last;
        }
    
        // 递归版本
        public int LastRemainingV3(int n, int m){
            if(m < 1 || n < 1) return -1;
    
            if(n == 1) return 0; // 出口
    
            return (LastRemainingV3(n-1, m) + m)%n;
        } 
        }

测试代码：

public class _Q45Test extends TestCase {
        
    
        _Q45<?> remain = new _Q45();
    
        public void test(){
            int n1 = 5;
            int m1 = 3;
    
            int n2 = 6;
            int m2 = 5;
    
            System.out.println(remain.LastRemaining(n1, m1));
            System.out.println(remain.LastRemainingV2(n1, m1));
            System.out.println(remain.LastRemainingV3(n1, m1));
    
            System.out.println(remain.LastRemaining(n2, m2));
            System.out.println(remain.LastRemainingV2(n2, m2));
            System.out.println(remain.LastRemainingV3(n2, m2));
    
        }
        }